Category Archives: Binary Trees

Path length between two binary tree nodes

Given a full binary tree (all nodes except leaf nodes have left and right child) represented as shown below.
If the root is labelled i, it’s left child is labelled 2*i and right child is labelled as 2*i+1.
1
/   \
2     3
/  \   / \
4  5  6   7

Given two nodes from this tree, how do we find the length of the path between them?
For example the path length between 2 and 3 is 2 (2->1->3)
Similarly path length between 4 and 1 is 2, and between 4 and 7 it is 4 (4->2->1->3->7)

In a binary tree, two nodes can be connected in two possible ways.

  • Either one of the nodes can be ancestor of the other, or
  • Both of them are connected by some common ancestor.

For example, take 1 and 5, 1 is an ancestor of 5.
Take 4 and 5, they are connected by their lowest common ancestor 2, so the path goes has to via 2.
So this problem can be solved by finding the Lowest Common Ancestor (LCA) of the two nodes and adding the distances between the nodes to their LCA.

We use the bottom up approach here. Start from the given two nodes and try to search for lowest common ancestor by going up since we can easily go the parent node by dividing the node by 2. While finding the LCA, we can also calculate the path length.

Since we traverse through the tree for at most the height of the tree, the time complexity will be O(log n).

Here is the C++ code.

Problem source: Codechef

Mirror-2Bimage-2Bbinary-2Btree

Mirror image of a binary tree

Given a binary tree, how to convert it to it’s mirror image?
For example consider the following binary tree and it’s mirror image.

Here simply, the left and right sub trees of each node are inverted. So we have to simply invert the given binary tree. It is a simple implementation problem. Using recursion we can solve it by following the below steps

  1. If root is NULL, simply return
  2. Invert the left sub tree
  3. Invert the right sub tree
  4. Swap left and right sub trees.

Here is the C++ code which implements the above algorithm. It runs in O(n) time.

Check if a binary tree is the mirror image of itself

Given a binary tree, how do we write a program to check if it is the mirror image of itself. This binary tree is also called a symmetric tree. 
A binary tree is called a symmetric tree if it’s left and right sub-trees are mirror images of each other.

For example Let us consider the following examples of some symmetric and asymmetric trees.

    1
   / Symmetric
  2   2  
    1
   / Asymmetric
  2   3 
      1
     /
    2   2  Symmetric
   /    
  3       3

We can design a recursive algorithm like the following.

  1. An empty tree is a symmetric tree.
  2. At each node we check the following
    1. If the left value and right value are same
    2. If the left sub-tree of left node and right sub-tree of the right node are mirror images
    3. If the right sub-tree of left node and left sub-tree of the right node are mirror images
  3. If all the above conditions are satisfied then the tree is symmetric.

Here is the C++ implementation of this.

Level order traversal of the binary tree from the bottom

Given a binary tree, how do we print the nodes in level order starting from the bottom.

For example for the following tree, the output should be 2 3 1

    1
  / 
 2    3

An obvious solution is to first find the maximum levels of the tree. we can print the nodes from maximum level to minimum level. This is not so efficient, because to print each level we need to traverse all the nodes.

Another solution is that we can modify the level order traversal. We need an additional stack to store the nodes. Instead of printing the values of the nodes as soon as they are deleted from the queue, we can add them to stack. Later, we can pop the elements from the stack and print them. This will print the elements in reverse level order.

Here is the C++ code for the second approach.


Checking if a binary tree is balanced

Given a binary tree, how do we check if it is balanced or not?
We say that a binary tree is balanced if height difference of left  and the right sub-trees is at most 1 at  any node.

Consider the following examples

  1          1               1             1
 /                       /              
2   3          2           2                 2
                                           /
                                          3
Balanced    Balanced     Balanced       Unbalanced

Solution:

We can simply implement a recursive solution based on the above definition of balance. At each node we check the height of the left sub tree and the right sub-tree and call the same function for it’s left child and right child recursively. But this is inefficient because we calculate the height repeatedly. This solution is O(n2).

Because we are calculating the height at each node, we can reuse the height of sub-tree to check the balance at the root node. Here is how we can do it. 

We write a method called balance. This method returns the actual height of the tree if it is balanced. Otherwise it returns -1. So at any point if the balance of left or right sub-tree is -1 or their difference is greater than 1, we can simply return false.

Here is the C++ implementation of this algorithm. It runs in O(n) time.

Binary-2Bsearch-2Btree

Finding the kth element in Binary search tree

Given a binary search tree, how do we find a kth smallest or kth largest element?
For example, given the following binary search tree.
Third largest element is 6
Second smallest element is 2
Fifth largest element is 5 and so on…

Solution:


We can solve this problem by modifying the the in-order traversal method of a binary tree. In addition to the root node, we can pass two more parameters one is K, and current count of the nodes visited as a reference parameter. When the current count reaches K we found the kth order element.

To find out the kth smallest element, we need to visit left sub-tree, then root and then the right sub-tree as usual. To find the kth largest element we need to do reverse in-order traversal i.e First visit right sub-tree, then root and then the left sub-tree.

Here is the C++ implementation. This includes the recursive and iteration versions of finding kth smallest and kth largest elements. The iterative version is simply the manual implementation of a recursion using a stack.

Right view of the binary tree

Given a binary tree, how do we print the right view of it?

For example, consider the simple binary tree below

   1
 /
2   3

The right view of this is 1, 3. Similarly consider one more example

            1
          / 
         2    5
        /  
       3   4 

Right view for this tree contains 1, 5, 4.

This is similar to my last post which asks for the left view of the binary tree. We just need to make the following changes to the algorithms discussed in the earlier post.

In case of iterative solution, we need to add the right child first to the queue before adding the left child.

In the recursive approach, we need to first recurse on the right child. Below is the modified code.
 

Left view of a binary tree

Given a binary tree, how do we print the left view of it?

For example, consider the simple binary tree below

   1
 /
2   3

The left view of this is 1, 2. Similarly consider one more example

            1
          / 
         2    3
             /
            4   5

Left view for this tree contains 1, 2, 4.

If the tree is completely left skewed or right skewed, the left view contains all the nodes like the following. For example

1                1
               /
  2            2
             /
    3        3

The left view for both of the above trees is 1, 2, 3.

We can solve this problem in two ways, one iterative and the other using recursion.

Recursive method:

In this approach to the traversal function, we send two additional parameters along with root node, one is the current level and another is maximum level. maximum level is a reference parameter which remembers it’s value between the function calls. 
We compare the current and maximum level values, if the max level is less than current level we print the data at root node and update the maximum level. Recursively call the same function for the left and right sub-trees by incrementing the current level.


Iterative method:

We use the level order traversal method to print the first node in each level. While storing the nodes in the queue, we store a separator (NULL) node to distinguish between the levels.


Here is the C++ code which implements the above approaches.Both run in O(n) time complexity.

Longest path in a binary tree

Given a binary tree, how do we find the longest distance between any two nodes in it? Some times this is referred to as the diameter of the tree.
For example consider the below binary tree

The longest path in this tree is 1 – 2 – 3 – 5 – 8 – 6 – 7. In this example the longest path passes through the root node. Sometimes it may not pass through the root. Checkout the next example.

The longest path 27-28-24-36-42-59-55 does not include the root node.

Here is how we can find the longest path recursively. We know that the height of the binary tree is the longest path from the root node to any leaf node.(Read this post to know more). Diameter is the maximum of the following.

Height(left subtree) + Height(right subtree) + 1
Diameter(left subtree)
Diameter(right subtree)

Here is the C++ implementation of the above. This program calculates the number of nodes on the longest path. The time complexity for this solution is O(n2). For optimal implementation, you can checkout this post.

Building a binary tree using inorder and post/pre order traversals

Given the in-order, and pre-order or post-order sequences of a binary tree, how do we construct a binary tree from them?

Given only pre-order and post order traversals, we can not construct a unique binary tree from them.

For example given 
In-order : {1, 2, 3, 4, 5, 6, 7, 8}
Pre-order: {5, 3, 2, 1, 4, 8, 6, 7}

We have to create the following binary tree

We use recursive approach for constructing a binary tree from In-order and Post-order or Pre-order traversals .

Constructing from Inorder and Preorder:

In Pre order, we first traverse the root, then left sub tree and right sub tree. So the first element in the pre order is always the root. We search for this element in the in-order sequence. This index divides the in-order sequence into left subtree and right subtree.

For example consider the following binary tree
                
                       1
               /  
              2     3
             /    /    
            4   5 6   7

Inorder:  {4, 2, 5, 1, 6, 3, 7}
Preorder: {1, 2, 4, 5, 3, 6, 7}

Create 1 as the root node, 

  • all the left elements to the left of it {4, 2, 5} form the left subtree
  • all the elements to the right of it {6, 3, 7} form the right subtree


We can use the index of 1 in Inorder (in this case 3) to calculate the size of the left and right subtrees.

Size(left subtree) = index
Size(right subtree) = size-index-1

We can also use this index to calculate the offset of Inorder and Post order sequences for the subtree.

To create the left subtree we pass Inorder:{4, 2, 5} Preorder:{2, 4, 5} as parameters to the recursive call.

To create the right subtree we pass Inorder:{6, 3, 7} Preorder:{3, 6, 7} as parameters.

Constructing from Inorder and Postorder:

In post order, we first traverse the left subtree, right subtree and visit the root. So the last element in the post order sequence is the root.
Similar to the above algorithm, this element divides the in-order sequence into left subtree and right subtree.

Considering the same example as above the Post order is {4, 5, 2, 6, 7, 3, 1}
Once we create the root with the last element i.e 1. 

We pass the following parameters to create the left and right subtrees.

                       Inorder                 Postorder
Left Subtree    {4, 2, 5}                {4, 5, 2}
Right Subtree   {6, 3, 7}                {6, 7, 3}

Here is the C++ implementation of the above two algorithms.