Binary trees are trees where every node has a maximum of two children. You may have one child or no child at all. An empty tree is also a valid binary tree.
TYPES OF BINARY TREES
Strict (or proper) Binary Trees
Each node has exactly two children or no children.
Complete Binary Tree
A complete binary tree is a binary tree where
- all levels except possibly the last are completely filled, and
- the last level has all its nodes to the left side (without any missing ones in between).
Note: There can be cases where a binary tree is
- strict and complete
- strict but not complete
- complete but not strict
- Not strict and not complete
Full (or Perfect) Binary Tree
Full binary tree is a binary tree where
- all leaves are at bottom of the tree and
- all non-leaf nodes has exactly two children.
Binary Search Tree (BST)
A Binary Search Tree (BST) is a binary tree where all nodes in the left sub tree of a node are less than (or equal to) the node and all nodes in the right sub tree of a node are greater than the node.