Trees: Important Formulas and Recursive Equations
Important formulas:
Number of unlabelled binary trees possible with n nodes = 2nCn/(n+1)
Number of labelled binary trees possible with n nodes = (2nCn/(n+1)) x n!
With n nodes and a given preorder, total number of binary trees possible = 2nCn/(n+1)
With a given inorder and any one of preorder or postorder, total numbar of binary trees possible = 1
For a complete n-ary tree having X internal nodes, the total number of leaves = X(n-1)+1
For a binary tree having n leaf nodes, total number of nodes of degree two = n-1
The maximum number of nodes in a binary tree of height 'h' = 2h+1-1
The minimum number of nodes in a binary tree of height h = h+1
Important Recursive Equations:
T- Pointer to the root of the tree
NN- Number of nodes
LST- Pointer to Left Sub Tree
RST- Pointer to Right Sub Tree
1.Counting number of nodes
| NN(T) = | 0; if T is Null |
| = | 1+NN(LST)+NN(RST);otherwise |
2.Counting number of leaves
| NN(T) = | 1; if T is leaf |
| = | NN(LST)+NN(RST);otherwise |
3.Height H of a binary tree
| H(T) = | 0; if T is Null or T is leaf |
| = | 1+max(H(LST),H(RST));otherwise |
4.Counting number of full nodes (FN) in a binary tree
| FN(T) = | 0; if T is Null or T is a leaf |
| = | FN(LST)+FN(RST); if T has only one child |
| = | 1+FN(LST)+FN(RST); if T is a full node |
5.Counting minimum number of nodes in an AVL tree of height h
| N(h) = | 1; if h=0 |
| = | 2; if h=1 |
| = | N(h-1)+1+N(h-2); otherwise |
Time Complexities :
| Operation | BST | Balanced BST |
| Search | O(n) | O(log n) |
| Finding Height | O(n) | O(log n) |
| Insertion | O(n) | O(log n) |
| Deletion | O(n) | O(log n) |