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)

 

Contributor's Info

Created: Edited:
0Comment