Complete Binary Trees

A complete binary tree is a binary tree that satisfies two properties. First, in a complete binary tree, every level, except possibly the last, is completely filled. Second, all nodes appear as far left as possible

In a complete binary tree Tn , there are exactly n nodes and level r of T can have at most 2r nodes.

level 0 has 20 = 1 node, level 1 has 21 = 2 nodes, level 2 has 22 = 4 nodes, level 3 has 6 nodes which is less than the maximum of 23 = 8 nodes

tree T13 has exactly 13 nodes. They have been purposely labelled from 1 to 13, so that it is easy for the reader to find the parent node, the right child node, and the left child node of the given node. The formula can be given as—if K is a parent node, then its left child can be calculated as 2 × K and its right child can be calculated as 2 × K + 1. For example, the children of the node 4 are 8 (2 × 4) and 9 (2 × 4 + 1). Similarly, the parent of the node K can be calculated as | K/2 |. Given the node 4, its parent can be calculated as | 4/2 | = 2. The height of a tree Tn having exactly n nodes is given as:

This means, if a tree T has 10,00,000 nodes, then its height is 21

Complete binary tree
Complete binary tree

Extended Binary Trees

A binary tree T is said to be an extended binary tree (or a 2-tree) if each node in the tree has either no child or exactly two children

Representation of Binary Trees in the Memory

Linked representation of binary trees In the linked representation of a binary tree, every node will have three parts: the data element, a pointer to the left node, and a pointer to the right node. So in C, the binary tree is built with a node type given below

struct node {
struct node *left;
int data;
struct node *right;

Leave a Comment