Types of binary tree

A binary tree is full if each node has 0 or 2 children. We can also say that a full binary tree is a binary tree in which all the nodes, except the leaves, have two children.

Here are examples of full binary trees.

A binary tree is complete if all the levels are completely filled, except maybe the last level and the last level has all the keys as left as possible.

A binary tree is perfect if all the internal nodes have two children and all the leaves are on the same level.

A perfect binary tree of height h a \(2^h - 1\) node.

A binary tree is balanced if its height is \(O(log n)\), where n is the number of nodes.

•   AVL trees maintains the height in \(O(log n)\) while ensuring that the difference between the heights of the left and right subtrees is 1.
•   The red-black trees maintain the height in \(O(log n)\) ensuring that the number of black nodes on each root-to-leaf path is the same and that there are no adjacent red nodes.

Binary balanced search trees are good from a performance point of view because they provide \(O(log n)\) time for searching, inserting and deleting.