Types of Binary Tree

By | January 17, 2016

Types of Binary Tree
Types of Binary Tree

Given below are different types of Binary tree :

Full Binary Tree:

A Binary Tree is full if every node has 0 or 2 children. Following are examples of full binary tree.

In a Full Binary, number of leaf nodes is number of internal nodes plus 1
Mathematically,
L = I + 1
Where,
L = Number of leaf nodes
I = Number of internal nodes

Complete Binary Tree:

A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

Practical example of Complete Binary Tree is Binary Heap.

Full and complete Binary Tree

Perfect Binary Tree

A Binary tree is Perfect Binary Tree in which all internal nodes have two children.
Hence, all leaves are at same level.
A Perfect Binary Tree of height, h has: 2h – 1 nodes.

Perfect binary tree

Example of Perfect binary tree is ancestors in family.
Keep a person at root, parents as children, parents of parents as their children.

Balanced Binary Tree

A binary tree is balanced if height of the tree is O(Log n) where n is number of nodes.
AVL trees maintain O(Log n) height by making sure that the difference between heights of left and right subtrees for any node is 1, -1 or 0.
Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths are same and there are no adjacent red nodes.
Balanced Binary Search trees are good performance wise as they support O(log n) time for search, insert and delete operations.

A Degenerate (or pathological/Skewed) Tree 

Skewed Binary Tree

A Tree where every internal node has one child. Such trees are performance-wise same as linked list.