Binary Tree and its Properties

By | February 5, 2016

Binary Tree and its Properties

Following are some properties of binary trees.

The maximum number of nodes at a given level, k of a binary tree is 2k-1.

Binary Tree Levels
Level of root is taken to be 1 above.
This can be proved by induction.
For root, k = 1
Therefore, number of nodes = 2k-1 = 1
Assuming that maximum number of nodes on level k is: 2k-1
Since in Binary tree every node has at most 2 children, next level would have twice nodes, i.e. 2 * 2k-1 = 2k nodes at most

Maximum number of nodes in a binary tree of height, h is: 2h – 1.

Height of a tree is maximum number of nodes on root to leaf path.
 Binary Tree height

A tree has maximum nodes if all levels have maximum nodes.
So maximum number of nodes in a binary tree of height h: 1 + 2 + 4 + .. + 2h-1.
Sum of this series: 2h – 1.
Note: If we take height of a leaf is considered as 0, the above formula becomes: 2h+1 – 1.

In a Binary Tree with n nodes, minimum possible height or minimum number of levels is: ceil(Log2(n+1) )

If we consider the convention where height of a leaf node is considered as 0, then above formula for minimum possible height becomes: ceil(Log2(n+1)) – 1

A Binary Tree with L leaves has at least: ceil(Log2L )+ 1 levels

A Binary tree has maximum number of leaves when all levels are fully filled. Let all leaves be at level k, then below is true for number of leaves L.
L <= 2k-1
Log2L <= k-1
k >= ceil(Log2L ) + 1

In a Binary tree, number of leaf nodes is always one more than nodes with two children.

L = T + 1
where,
L = Number of leaf nodes
T = Number of internal nodes with two children