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
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;
};