# 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 2**^{k-1}.

^{k-1}.

Level of root is taken to be 1 above.

This can be proved by induction.

For root, k = 1

Therefore, number of nodes = 2^{k-1} = 1

Assuming that maximum number of nodes on level k is: 2^{k-1
}Since in Binary tree every node has at most 2 children, next level would have twice nodes, i.e. 2 * 2^{k-1 }= 2^{k }nodes at most

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

^{h}– 1.

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

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 + .. + 2^{h-1}.

Sum of this series: 2^{h} – 1.

**Note:** If we take height of a leaf is considered as 0, the above formula becomes: **2**^{h+1}** – 1.**

**In a Binary Tree with n nodes, minimum possible height or minimum number of levels is: ceil****(Log**_{2}(n+1) )

_{2}(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(Log_{2}(n+1)) – 1

**A Binary Tree with L leaves has at least: ceil(Log**_{2}L )+ 1 levels

_{2}L )+ 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 <= 2^{k-1
}Log_{2}L <= k-1

k >= ceil(Log_{2}L ) + 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