How can I find the common ancestor of two nodes in a binary tree?
- by Siddhant
The Binary Tree here is not a Binary Search Tree. Its just a Binary Tree.
The structure could be taken as -
struct node {
int data;
struct node *left;
struct node *right;
};
The maximum solution I could work out with a friend was something of this sort -
Consider this binary tree (from http://lcm.csa.iisc.ernet.in/dsa/node87.html) :
The inorder traversal yields - 8, 4, 9, 2, 5, 1, 6, 3, 7
And the postorder traversal yields - 8, 9, 4, 5, 2, 6, 7, 3, 1
So for instance, if we want to find the common ancestor of nodes 8 and 5, then we make a list of all the nodes which are between 8 and 5 in the inorder tree traversal, which in this case happens to be [4, 9, 2]. Then we check which node in this list appears last in the postorder traversal, which is 2. Hence the common ancestor for 8 and 5 is 2.
The complexity for this algorithm, I believe is O(n) (O(n) for inorder/postorder traversals, the rest of the steps again being O(n) since they are nothing more than simple iterations in arrays). But there is a strong chance that this is wrong. :-)
But this is a very crude approach, and I'm not sure if it breaks down for some case. Is there any other (possibly more optimal) solution to this problem?
