Category Archives: Binary Trees

Counting the number of leaf nodes in a binary tree

Given a binary tree, write a program to count the number of leaf nodes. A leaf node is a node which does not have left and right children.

For example consider the following binary tree.

It has 3 leaf nodes namely 1, 4 and 7.

The solution is simple. The number of leaf nodes of a binary tree rooted at R is the sum of leaf nodes in the left and sub trees. Using this property we can devise a simple recursive solution.

This can also be solved using iterative solution by traversing the binary tree using BFS (Breadth First Search) traversal.

The following C++ program shows both recursive and iterative implementations.

Check if two binary trees are identical

Given two binary tress, how do we check if they are identical in structure, and  contents?
For example the following two binary trees are identical.
We can solve this problem using recursion effectively. The function checks if the root element is equal and use the same function to check if it’s left and right sub-trees are also identical. If it is we return true. 

Here is the C++ function.

bool isSameTree(TreeNode *p, TreeNode *q) {
if( p && q )
{
if( p->val != q->val )
return false;

return ( isSameTree(p->left,q->left) && isSameTree(p->right,q->right) );
}
else if( !p && !q)
return true;
else
return false;
}

Level order traversal of a binary tree

Given a binary tree, we have to print the data level wise. 
For example level order traversal of the following tree produces the sequence 5,3,8,2,4,6,1,7.
The hint to solve this problem is to use a Queue data structure. We start by inserting the root node into the queue. Until the queue is empty, we remove the first element from the queue and insert it’s left and right children at the last.

This will give us the level order traversal of the binary tree. For example look at the queue state at each iteration.
5
3,8
8,2,4
2,4,6
4,6,1
Here is the C++ program which contains the level order traversal function.

Traversals of a binary tree

Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure.

There are three main traversals of the binary tree. Namely

  • In-order traversal
  • Post-order traversal
  • Pre-order traversal
In addition to these, there are inverses of the above algorithms, and there is a level order traversal.

In this post we will see the three main traversal algorithms mentioned above. All of these are defined as recursive algorithms.
In In-order traversal, we first visit the left sub-tree, then root, and then the right sub-tree.
In Post-order traversal, we first visit the left sub-tree, then the right sub-tree, and then the root.
In Pre-order traversal, We first visit the root, then visit the left sub-tree and then visit the right sub-tree.

For example consider the simple  3 node binary tree

In-order traversal: B  A  C
Post-order traversal: B  C  A
Pre-order traversal: A  B  C

To consider a bigger example, take the following binary search tree and it’s traversal sequences for the three algorithms.

In-order: 1  2  3  4  5  6  7  8

Post-order: 1  2  4  3  7  6  8  5
Pre-order: 5  3  2  1  4  8  6  7 
The in-order traversal of the binary search tree always produces the sorted order of it’s elements.

Here is the C++ code for all the traversals.