##### 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)