trees-take-2
Trees
Binary Tree
1 root, 2 nodes each - left node, right node.
Complete Binary Tree
All nodes have left and right child, except the last level, which may have left, then right node.
Full Binary Tree
All nodes have left and right child, except the last level, where nodes have NO children.
For a tree of height h:
- total no. of nodes in full binary tree >= 2h + 1
- total no. of nodes in full binary tree <= 2^(h+1) - 1
Perfect Binary Tree
When all nodes have 2 children (except the last one which has none) and all leaves are at the same level.
For a tree of height h:
- total no. of nodes in full binary tree == 2h + 1
- total no. of leaf nodes = 2^h or (n+1)/2
More types of Binary trees:
- Complete Binary Tree
- Skewed Binary Tree
- Binary Search Tree (BST)
- AVL Tree