Wednesday, 12 July 2017 10:54

## Binary Tree | Set 2 (Properties)

Written by
Rate this item

1) The maximum number of nodes at level ‘l’ of a binary tree is 2l-1.
Here level is number of nodes on path from root to the node (including root and node). Level of root is 1.
This can be proved by induction.
For root, l = 1, number of nodes = 21-1 = 1
Assume that maximum number of nodes on level l is 2l-1
Since in Binary tree every node has at most 2 children, next level would have twice nodes, i.e. 2 * 2l-1

2) Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1.
Here height of a tree is maximum number of nodes on root to leaf path. Height of a leaf node is considered as 1.
This result can be derived from point 2 above. A tree has maximum nodes if all levels have maximum nodes. So maximum number of nodes in a binary tree of height h is 1 + 2 + 4 + .. + 2h-1. This is a simple geometric series with h terms and sum of this series is 2h – 1.
In some books, height of a leaf is considered as 0. In this convention, the above formula becomes 2h+1 – 1

3) In a Binary Tree with N nodes, minimum possible height or minimum number of levels is  ⌈ Log2(N+1) ⌉
This can be directly derived from point 2 above. If we consider the convention where height of a leaf node is considered as 0, then above formula for minimum possible height becomes   ⌈ Log2(N+1) ⌉ – 1

4) A Binary Tree with L leaves has at least   ⌈ Log2L ⌉ + 1   levels
A Binary tree has maximum number of leaves when all levels are fully filled. Let all leaves be at level l, then below is true for number of leaves L.

```   L   <=  2l-1  [From Point 1]
Log2L =   ⌈ Log2L ⌉ + 1  ```

5) In 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```

See Handshaking Lemma and Tree for proof.

In the next article on tree series, we will be discussing different types of Binary Trees and their properties. 