Binary Trees

Lets discuss binary tree concepts and few basic frequently asked programming questions related to it.

Binary tree is tree in which each node can have at the most two children. This means each node can have 0 children (leaf node) , 1 children or two children. Generally referred as left child and right child. In terms, both left sub-tree and right sub-tree are also binary trees.

Complete Binary tree:  A binary tree in which all the levels are complete filled except last level which is filled from left to right.

Balanced Binary tree:  A binary tree in which difference between the height of left sub-tree and right sub-tree is 0 or 1

Perfect or Full Binary tree:  A binary tree in which each node have exactly 0 or 2 nodes.

A complete binary tree and a perfect binary tree is always going to be balanced binary tree.

Height of Binary tree: 

Lets consider ‘n’ total number of nodes in balanced binary tree and ‘l_k‘ is the numbers nodes at level ‘l’.

So, for k = 0 -> l₀ = 1  (root node)

for k = 1 -> l₁  =  2 (second level)

for k = 2 -> l₂  = 4  (second level) and so on..

This means each node will have twice number of nodes from its previous level. Total number of nodes can be represent using this concept as:

2⁰  + 2¹ + 2²  +2³ +2⁴ +……+ 2^h = n      here h is a height of tree

So,  2^h+1   -1   = n           (for understanding, 2⁰⁺¹ -1 -> 2¹ – 1 =1 for level 0 and so on..for each level we can compute)

Now, we will calculate hight of balanced binary tree if has n nodes using above expression:

2^h+1 = n+1

h+1 = lg(n+1)

h= lg(n+1) – 1

By l’Hopital’s rule this expression follows as:  lg(n+1) – 1 = lg(n)

So, h = lg(n)

In binary tree, a minimum height of tree for ‘n’ nodes can be |_lg(n)_|  (ceiling function) and maximum height can be (n-1).

A perfect binary tree of height h has 2^h leaf nodes in terms of height and has (n+1)/2 leaf nodes in terms of ‘n’.

Tree Traversal:

Traversal means visiting each node of a tree. Linear data structure like array, we traverse it in one direction starting from 0 index to last index of array. However, tree can be traversed in different ways.

Level Order Traversal: This is also known as breadth first traversal. Every node on a level before going to a lower level.

Depth First Traversal:  This traversal can be done in three ways, In-order, Pre-order and Post-order.

Inorder traversal: <left><root><right>

1. Traverse left sub tree.

2. Print data in root.

3. Traverse right sub tree.

Inorder traversal is used in binary search tree we get numbers sorted in sorted ascending order.

Preorder traversal: <root><left><right>

1. Print data in root.

2. Traverse left sub tree.

3. Traverse right sub tree.

By using preorder traversal  we can make a copy of a tree.

Postorder traversal: <left><right><root>

1. Traverse left sub tree.

2. Traverse right sub tree.

3. Print data in root.

Postorder traversal is used when we want to delete a tree as we visit parent node after visiting its children.

Note: To remember traversals simple method is to remember position of root with respect to prefix of name of traversal.

Implementation of traversals:

Inorder traversal:

Preorder traversal:

Postorder traversal:

In each traversal every node of a tree is visited so time complexity  for tree traversal in O(n).

You can find more coding questions and solutions here.

Lets discuss about binary search tree in next session..