Properties of Binary Tree

 Important properties of binary trees are-

Property-01

Minimum number of nodes in a binary tree of height H

= H + 1

 Example

 

To construct a binary tree of height = 4, we need at least 4 + 1 = 5 nodes 

 

Property-02

 

Maximum number of nodes in a binary tree of height H

= 2^H+1 – 1

Example

Maximum number of nodes in a binary tree of height 3

= 2³⁺¹ – 1

= 16 – 1

= 15 nodes

Thus, in a binary tree of height = 3, maximum number of nodes that can be inserted = 15.

 

Property-03

 

Total Number of leaf nodes in a Binary Tree

= Total Number of nodes with 2 children + 1

 Example

Here,

• Number of leaf nodes = 3
• Number of nodes with 2 children = 2

 

Clearly, number of leaf nodes is one greater than number of nodes with 2 children.

This verifies the above relation.

 

Property-04

 

Maximum number of nodes at any level ‘L’ in a binary tree

= 2^L

 Example

 

Maximum number of nodes at level-2 in a binary tree

= 2²

= 4

Thus, in a binary tree, maximum number of nodes that can be present at level-2 = 4.