Binary Trees
A tree whose elements have at most 2 children is called a binary tree. Since each node in a tree can have only two children, we typically name them the left and right child.
The binary tree node contains following parts,
Full Binary Tree – A binary tree in which each node has exactly zero or two children is called a full binary tree. In a full tree, there are no nodes with exactly one child.
Complete Binary Tree – A binary tree in which is completely filled, with the possible exception of the bottom level. The tree is filled from left to right. A complete binary tree of the height h has between 2h and 2(h+1)-1 nodes.
Binary Search Trees
A tree whose elements have at most 2 children is called a binary tree. We name two children right and left nodes, as each element in a binary tree can have only two children.
The structure representation of Binary Tree is shown below:
+91-4446311234
+1-6502652492
+91-7530088009
struct node
{
int data;
struct node *left;
struct node *right;
}
Properties of Binary Tree
The following are the properties of Binary Tree:
Here level is a number of nodes on path from root to the node (including root and node). Level of root is 1.
For example, l = 2, number of nodes = 2^(2-1) = 2^1 = 2
Since binary node has at most 2 children, the level 2 contains 2 nodes; the level 3 contains 4 nodes and so on.
Here height of a tree is a maximum number of nodes from root to leaf path. Height of a tree with single node is considered as 1. The tree can have maximum nodes, if all the levels have maximum nodes.
The maximum number of nodes in a binary tree of height h is 1+2+4+8+….+2^(l-1), where level is a number of nodes on path from root to the node. Hence, the maximum number of nodes in a binary tree is given by the geometric series with height h is 2^(h – 1).
For example, h=3, number of nodes = 2^3 – 1 = 8-1 = 7.
This is directly derived from the point 2 above. If the height of the leaf node is considered as 0, then above formula for minimum possible height becomes Log2(N+1)
A Binary tree has maximum number of leaves when all the leaves are fully filled. Let all the leaves be at level l, then below is true for number of leaves L.
l <= 2^(l-1)
l = Log2L + 1
where l is the minimum number of levels
L = T + 1
Where L = Number of leaf nodes
T = Number of internal nodes with two children.
