18 August 2010

Puzzle - "Find Common Parent"


There is a binary tree. Each node has id, left and right as data. The id is unique integer representing the node, left and right are pointers/references points to left and right child respectively. Given two integers, write an algorithm/program to find the lowest common parent node.

Input - {15, 10}, Output should be {2}
Input - {19, 15}, Output should be {4}
Input - {6, 20}, Output should be {}


Suren said...

- Find the path of the node from the root or from node -> root.

- Do the intersection of the two paths and we will have common parent

The traversal can be breadth or depth first. In both cases it will order of the height.

Some questions Is it an ordered binary tree ? If we make this assumption, then the breadth first traversal will give faster results.

Lakshmi Narayanan N said...


The tree is not ordered.

Suren said...

Ok ! Even if it's not ordered, then the traversal from node -> root and common inter-section will give the result

ArunMozhi said...
This comment has been removed by the author.
ArunMozhi said...

thanks for u r reply.,
i think we want to split every node of the least left and right as individual array set combination,after that we should find the place of the input nodes of two array in the array set ,after that we can find by compare the every element of the two array.