Finding lowest common ancestor in Binary Tree

general
, ,
1

This is not like other Codechef questions but still very interesting.
How do we find lowest common ancestor in Binary Tree in O(n) time provided that you do not have any extra memory to store parent pointer at every node?

2

A very clear explanation provided in this video… just watch it

1 Like
3

@sumanth232 This video is good.! but i didnt got how that step is O(n). The 2 traversal are of Theta(n) but not getting how that last step is order n.

4

@msehgal Here is a bottom up approach for finding LCA. We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.

Code:

 Node *LCA(Node *root, Node *p, Node *q) {

  if (!root) return NULL;  

  if (root == p || root == q) return root;

  Node *L = LCA(root->left, p, q);

  Node *R = LCA(root->right, p, q);

  if (L && R) return root;  // if p and q are on both sides

  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Time Complexity : O(n)

Source.

1 Like
5

very nice answer…!! Its very good…!! Thanks @argonaut

6

@msehgal Thank you!! :slight_smile:

7

I think there’s another method which involves an euler tour(dfs without checking for the already visited condition) and range minimum query.Its quite simple if you are comfortable with segment trees(another important data structure generally seen in codechef questions).Here’s the link:lca using rmq

Implementing the above solution willhelp you learn about lca as well as segment trees.

1 Like
8

nice one.!!

9

go to link Static treesthis will help you a lot.

10

This solution is incorrect.
Let’s say you want to search 5 and 9 in the tree and 9 is not present , this code doesnt work…

 4

5 10

For this tree , the above code returns 5 which is incorrect, there is no ancestor at all…

11

you are asking for linklist that’s right but for array there exit such type of question in codechef :slight_smile: same logic but they are asking about minimum path length instead of ancestor

you may check out this https://www.codechef.com/problems/BINTREE

12

Let the Binary Tree be like

                                   5
                                 /   \
                                1      7
                                 \       \
                                  2       15
                                   \       / 
                                    3     9
                                        /   \
                                       8    14
                                      /
                                     7

LCA of x and y is possible when a node say n lie between x and y i.e (x<n<y).
let x = 7 and y = 14
LCA is lca
Suppose we need to find the lca between x and y.
The lca will the one which has one of the value(x or y) to its left and the other to its right.
means x<lca<y  , if the condition is true then the node lca will be the LCA of x and y.



struct node *LCA(struct node *root , node *x , node *y)
{
      if(root==NULL) return null;
      if((root->data)>x && (root->data)>y) return(root->left , x , y);//x and y will lie on the left side.
      if((root->data)<x && (root->data)<y) return(root->right ,x ,y);//x and y will lie on the right side.
      return root; // return the LCA of x and y

}