Category Archives: Data structures

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.


Creating a balanced binary search tree from sorted array

Given a sorted array, how do we create binary search which height balanced.

For example the array [1,2,3,4,5] must be transformed to the following binary tree

                           3
                / 
               2    4
              /       
             1        5

We can use the divide and conquer approach to solve this problem. To create a balanced tree, the number of nodes on the left sub-tree should be almost equal to that of right sub-tree.

How do we do it?
 

The create method is provided the lower and higher index parameters in addition to the actual array. We create the root node with the middle element and create the left and right sub trees with the left and right portions of the array.

Here is the C++ code.

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.
 

Alternate arrangement of two linked lists

Given two linked lists, we have to merge them into a single list by alternatively taking one node from each list.We should do this by re-arranging the links and should not create duplicate nodes while merging.

For example consider the two lists

1 -> 2 -> NULL
3 -> 4 -> NULL

The result should look like the following.

1 -> 3 -> 2 -> 4 -> NULL.

There is no logic required for this problem except arranging the links carefully. 

Just take two pointers to the two lists, keep adding the first node followed by the second node by advancing both the pointers at a time. 

Come out from the loop when we reach the end of any list.


Lastly copy the remaining nodes from the longer list to the result list.

Below is the C++ implementation of the same. The program can be run through the following test cases.

  1. Two empty lists
  2. One empty list and the other non-empty list
  3. Two lists are of equal length
  4. Two lists are of unequal length

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.