Puzzle
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.
Example:
Input - {15, 10}, Output should be {2}
Input - {19, 15}, Output should be {4}
Input - {6, 20}, Output should be {}
5 comments:
- 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.
@Suren
The tree is not ordered.
Ok ! Even if it's not ordered, then the traversal from node -> root and common inter-section will give the result
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.
Post a Comment