Category Archives: 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

Finding the depth of n-ary tree given parent id representation

Given an a rooted n-ary tree represented as a parent id array, Write a program to find the depth of it.
 

The depth of a tree is defined as the maximum length of the path from root to any leaf node.

For example the following tree has a depth of 2 (for the path 0-2-4)

It is represented in parent id array as follows
index:    0  1  2  3  4
parent:  -1  0  0  0  2

This can be solved by first finding the depth of each node and returning the maximum among them. We can find the depth of each node by traversing the parent ids until we reach the root node. But this method takes O(n2) time if we naively calculate the depth of each node.

For example we calculate the depth of node 0 every time when we calculate the depths of it’s descendants (1,2,3,4).

We need to use a simple memorization (Dynamic Programming) to store the depths of nodes already calculated.

For example if we already have the depth of 2, then the depth(4) is depth(2)+1.

This method runs in O(n) time because each node is visited exactly once. space complexity is O(n).

The following is a C++ implementation of the above DP algorithm.