Binary tree
A Binary tree is the tree that can have two children.
We can use the following example to explain it
The node 1 has two pointers, which are left and right. The second node has two pointers, which are left and right. The third and fourth leaf nodes have the same pointer count as the first two.
Properties of a binary tree
- The maximum number of nodes in a binary tree is 2^i, given i is the respective level.
- The maximum number of nodes possible at height h is (20 + 21 + 22+….2h) = 2h+1 -1, where height is the longest path from the root node to the leaf node.
- The maximum number of nodes is h+1, where h is the height.
- Height of the node is inversely proportional to the number of nodes. If the height of the node is maximum, then the number of the nodes will be minimum.
Types of binary tree
There are four types of binary tree:
- Full/Proper/Strict Binary tree
- Complete Binary tree
- Perfect Binary tree
- Degenerate Binary tree
- Balanced Binary tree
Reference