Binary Tree
Definitions In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child . Properties 1. The maximum number of nodes at level $i$ of a binary tree is $2^{i-1} (i \geqslant 1)$ or $2^i(i \geqslant 0)$. Here level is the number of nodes on the path from the root to the node (including root and node). Level of the root is 1. Proof: Let, the maximum number of nodes on level i is S(i) = $2^{i-1}$ S(1) = $2^{1-1}$ = $2^0$ = 1 (By substituting $i$ = 1 on both sides) $\therefore$ S(1) is true. Let, S(i) be true for some natural number k. i.e., S(k) = $2^{k-1}$ Now, Since in Binary tree every node has at most 2 children, next level (k+1) would have twice nodes. i.e., S(k+1) = 2* S(k) = 2 * $2^{k-1}$ = $2^{(k-1)+1}$ = $2^k$ = $2^{(k+1)-1}$ ...