Lowest Common Ancestor of a Binary Tree Part I

July 18, 2011 in binary tree

Given a binary tree, find the lowest common ancestor of two given nodes in the tree.


        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous post: Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.

Hint:
Top-down or bottom-up? Consider both approaches and see which one is more efficient.

A Top-Down Approach (Worst case O(n2) ):
Let’s try the top-down approach where we traverse the nodes from the top to the bottom. First, if the current node is one of the two nodes, it must be the LCA of the two nodes. If not, we count the number of nodes that matches either p or q in the left subtree (which we call totalMatches). If totalMatches equals 1, then we know the right subtree will contain the other node. Therefore, the current node must be the LCA. If totalMatches equals 2, we know that both nodes are contained in the left subtree, so we traverse to its left child. Similar with the case where totalMatches equals 0 where we traverse to its right child.

What is the run time complexity of this top-down approach?

First, just for fun, we assume that the tree contains n nodes and is balanced (with its height equals to log(n) ). In this case, the run time complexity would be O(n). Most people would guess a higher ordered complexity than O(n) due to the function countMatchesPQ() traverses the same nodes over and over again. Notice that the tree is balanced, you cut off half of the nodes you need to traverse in each recursive call of LCA() function. The proof that the complexity is indeed O(n) is left as an exercise to the reader.

What if the tree is not necessarily balanced? Then in the worst case the complexity could go up to O(n2). Why? Could you come up with such case? (Hint: The tree might be a degenerate tree).

A Bottom-up Approach (Worst case O(n) ):
Using a bottom-up approach, we can improve over the top-down approach by avoiding traversing the same nodes over and over again.

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.

Sounds complicated? Surprisingly the code appears to be much simpler than the top-down one.

Notes:
The LCA problem had been studied extensively by many computer scientists. There exists efficient algorithms for finding LCA in constant time after initial processing of the tree in linear time. For the adventurous reader, please read this article for more details: Range Minimum Query and Lowest Common Ancestor in Topcoder.

Further Thoughts:
What if each node in the binary tree has a link to its parent? Could you devise a non-recursive approach without using extra space?

» Continue reading Lowest Common Ancestor of a Binary Tree Part II.

VN:F [1.9.22_1171]
Rating: 4.5/5 (65 votes cast)
Lowest Common Ancestor of a Binary Tree Part I, 4.5 out of 5 based on 65 ratings

45 responses to Lowest Common Ancestor of a Binary Tree Part I

  1. “we assume that the tree contains n nodes and is balanced (with its height equals to log(n) ). In this case, the run time complexity would be O(n). ”

    i think this is similar as O(n) time in making a heap..the prove can be found in CLRS page135

    VA:F [1.9.22_1171]
    +2
    • how can you see?

      VN:F [1.9.22_1171]
      0
      • find left count
        if left count == 2 => go left
        if left count ==1 => find right count (cant take it for granted that the other node is also present)
        if left count ==0 => find right count

        so worst case we traversed n nodes
        but we reduce the sub problem by half if both the nodes are present on left or right side

        so we get number of operations in each recursion as

        n + n/2 + n/4 + .. 1

        = n(1+1/2+1/4+… 1/2^lgn)
        as we know 1 +1/2 +1/4 +… inifinity = 2
        we get n*k where k>1 but <2
        so T(n) for top down approach = O(n)

        VA:F [1.9.22_1171]
        +2
    • What if one of the search node not present in tree? Still this(bottom up algy) code works?

      VA:F [1.9.22_1171]
      -1
  2. One C++ question here:
    If you are having Node* root, Node* p here, how did you overload the “==” operator to directly use them like if(root == p)?

    VA:F [1.9.22_1171]
    0
    • All pointers in C++ are just 32-bit unsigned integer values, so you don’t need to overload the “==” operator to do comparison.

      VN:F [1.9.22_1171]
      0
      • I see, so the assumption here is that the nodes pointed by p and q should be exactly the same objects to be found in the binary tree.

        VA:F [1.9.22_1171]
        0
  3. I think there is a small bug in Top-Down Approach. According to the definition of LCA, it allows a node to be a descendant of itself. So when node p = q (p or q is not the root), the LCA should be itself. But your approach figures out the root as the LCA.

    VA:F [1.9.22_1171]
    +1
  4. What is the running time of the bottom-up approach please?

    VA:F [1.9.22_1171]
    0
  5. O(n)

    VA:F [1.9.22_1171]
    0
  6. Genius!!

    VA:F [1.9.22_1171]
    0
  7. I don’t think the bottom-up approach code is *correct*, in the sample tree, find LCA(root, 5, 9) returns 5, it should be null.

    VA:F [1.9.22_1171]
    0
    • i don’t think it correct either, LCA(root,5,4) return 5 but its internal logic does not reflect finding node 4 there. aslo LCA(root,5,NULL) also return 5

      VN:F [1.9.22_1171]
      0
    • Given a binary tree, find the lowest common ancestor of “two given nodes in the tree”.

      The two nodes must be in the tree according to the question.

      VN:F [1.9.22_1171]
      +1
      • If both the nodes are already found in one of the subtrees of root, it does traversal again in vain. May be a static variable will be suffice to check, if subtree traversal is required or not

        VA:F [1.9.22_1171]
        0
    • I think the input in this question is two nodes whose LCA we need to find. So, the case where one of the node is incorrect does not arise. Thus, i think the solution is correct only.

      VA:F [1.9.22_1171]
      +1
  8. Will the bottom up approach work if there are duplicate elements in the tree, and we are looking for LCA of elements with one of them being duplicate?

    VA:F [1.9.22_1171]
    0
    • I think it doesn’t matter. Since “given nodes in the tree” means pointer, not the value in the tree

      VN:F [1.9.22_1171]
      0
  9. wael said on May 3, 2012

    you are assuming that both nodes exist in the tree which is not always the case.

    VA:F [1.9.22_1171]
    0
  10. can you please tell me,how to find out the lca of two given nodes in n-ary tree?

    VA:F [1.9.22_1171]
    +1
  11. if p or q is not in the tree, this will still return the ancestor of the existing one

    we won’t touch both p and q because of this line

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

    consider a tree like this

    1
    / \
    3 4
    \
    7
    / \
    6 8

    let p = 4 q = 8, when we reach 4, we will return, and 8 will never be visited.

    VA:F [1.9.22_1171]
    0
    • no this will work correctly .
      first 8 would we visited then as LCA(root->left, p, q); will go left then after traversing left subtree of 1 will visit right subtree and then following condn hlds
      if(L && R)
      return root

      VN:F [1.9.22_1171]
      0
  12. The bottom up approach has one bug.
    For eg: let us assume the tree is
    inorder : 1 3 4 5 8 9 10 15
    preorder : 10 8 4 3 1 5 9 15

    try to find the lca(4,40) :- function will return 4 as the answer, which is incorrect as 40 is not at all in the tree.

    this error occurs whenever there will be one of p or q present in the tree and other is not, because in line 2, we check that if root’s value is either equal to p or q, then return and we didn’t check for the other number.

    I try to solve this problem…but can’t able to fix this…….so guys help me in fixing this issue…

    thanks 1337c03dr for ur nice solutioin.. :)

    VA:F [1.9.22_1171]
    0
  13. the bottom up approach won’t work if the binary tree has duplicate element.
    suppose there are two 2′s and LCA is to be calculated of (2,10) as —
    5
    / \
    3 6
    / \
    2 2
    / \
    8 7
    it would return add of 3
    correct if i am wrong

    VN:F [1.9.22_1171]
    0
  14. LCA of a Binary Search Tree is easier as shown here,
    http://www.ritambhara.in/lowest-common-ancestor-in-binary-search-tree/

    VA:F [1.9.22_1171]
    0
  15. @Mridul, to solve the problem of one of node is not in the tree

    int LCA(N* n, N* a, N* b, N*& head)
    {
    if(!n || !a || !b) return 0;

    int l = LCA1(n->l, a, b, head);
    int r = LCA1(n->r, a, b, head);

    if(l==2 || r == 2)
    return 2;
    else if((l==1 && r == 1)
    ||( (l == 1 || r == 1 ) && (n == a || n == b)) )
    {
    head = n;
    return 2;
    }
    else if(n==a || n == b)
    return 1;
    else
    return max(l,r);
    }

    VA:F [1.9.22_1171]
    0
  16. i think if the problem with the bottom up algo is just the case when one of the nodes doesn’t exist, then we can just do a pre check for the existance of both nodes in o(N), by calling the counting function of the top-down approach on the root, and checking if the return value is 2.

    VA:F [1.9.22_1171]
    +1
  17. agree with Sanjay Pandey
    the bottom up approach won’t work if the binary tree has duplicate element.

    VA:F [1.9.22_1171]
    0
    • For babycandy and Sanjay, maybe you guys misunderstand the problem.
      In the problem, we just consider the node itself(not the data element of the node), which is a pointer. In Sanjay’s example, it’s not duplicated. The two nodes with data element 2 are different nodes.

      VN:F [1.9.22_1171]
      0
  18. Top down worst case O(n)

    DFS and return the stack of nodes from bottom to root of all nodes in the path of each node{first adn second}.

    Then do a merge like procedure by popping off the excess elements of one stack and then successively popping until both the stacks have the same top.

    VA:F [1.9.22_1171]
    +1
  19. What if one of the search node not present in tree? Still this(bottom up algy) code work?

    VA:F [1.9.22_1171]
    0
  20. My attempt though in C# this solves the extreme edge case of one of the nodes not present in tree while keeping botom up approach intact
    public Node LCA(Node Root,Noe P,Node Q,Ref bool Pbool,ref bool Qbool)
    {
    if (Root==null||P==null||Q==null)

    L = LCA(Root.Left,P,Q, ref Pbool, ref Qbool);
    R = LCA(Root.Left,P,Q, ref Pbool, ref Qbool);
    if(P==Root)
    Pbool = true; // identify if both the values are identified in the tree before spitting out LCA
    Return Root;

    if (Q ==Root)
    Qbool = true; // identify if both the values are identified in the tree before spitting out LCA
    Return Root;
    Return L==null?R:L;
    }

    VA:F [1.9.22_1171]
    0
  21. To 1337c0d3r:
    1. Assuming 2 nodes already in tree. This question has been asked by a lot of people not only here but also in the one for BST. You should put it clearly in your post that you make this assumption or better yet, do not make this assumption and provide code works for these cases.
    2. You are using the return value is null or not as an indicator if you found at least one value in one side of the tree. Simply change it to a structure that has a node and 2 boolean values, you can know if you found one node and which node or both nodes on one side of the tree. And you can avoid call the other side of the tree.

    VN:F [1.9.22_1171]
    0
    • re. 2: it should be fine, because it avoids traversing further in one side of tree by traversing other side of tree instead.

      VN:F [1.9.22_1171]
      0
  22. for the Bottom-up Approach, if p is not in the tree, but q is, it returns the root as LCA, which does not make sense. Should it return null in this case?

    VN:F [1.9.22_1171]
    0
  23. If the p and q are the same pointer. The result will be wrong.Actually.

    Di

    VA:F [1.9.22_1171]
    0
  24. The following code takes care of all the cases.. Enjoy. :) :)

    VA:F [1.9.22_1171]
    +1
  25. I have one simple approach which is based on post-order of binary tree traversing.

    struct tree {
    struct tree *l, *r;
    int key;
    };

    static int n1 = 0, n2 = 0; //0: the given node not visited, 1: the given node visted
    static struct tree *a1, *a2; //give two nodes

    static void visit(struct tree *t)
    {
    if (t == a1)
    n1 = 1;
    if (t == a2)
    n2 = 1;
    }

    void lca(struct tree *root)
    {
    int a1, a2;

    a1 = n1;
    a2 = n2;

    if (!root) return;

    lca(root->l);
    lca(root->r);
    visit(root);

    if (!a1 && !a2 && n1 && n2) {
    printf(“lca of n1 & n2 is node %d\n”, root->key);
    exit(0)
    }
    }

    VN:F [1.9.22_1171]
    0
  26. Sean said on May 8, 2014

    The above solution of the top-down apporach has one bug in countMatchesPQ() when p and q are equal nodes. When p equals q, the LCA is p/q itself.
    However, the above top-down solution will return the parent of p/q. Thus, countMatchesPQ() should be modified as below.

    VA:F [1.9.22_1171]
    0
  27. appears much more like a slipper than a sneaker nike TN homme . The concept for your Totally free was born following two Nike researchers, going to the Stanford track group, discovered that their sponsored runners ran sprints barefoot. ;We discovered pockets of individuals throughout the world who’re nonetheless operating barefoot, and what you discover is the fact that throughout propulsion and landing they’ve significantly much more variety of movement within the foot and engage much more with the toe, their feet flex, spread, splay and grip the surface, which means you’ve much less pronation and much more distribution of stress.; stated Jeff Pisciotta, the senior researcher in the Nike Sports activities Study Lab in Beaverton, Ore., who headed the Nike Air Max 2010 Totally free undertaking. Even so Wholesale Air Max 2009 has by no means offered up their method to Nike Air Max footwear, from Air Jordan footwear turn out to be well-liked, Nike has launched new pair every year.

    VN:F [1.9.22_1171]
    0
  28. personal vaporizer Lowest Common Ancestor of a Binary Tree Part I | LeetCode

    VA:F [1.9.22_1171]
    0
  29. herbal vaporizer pen Lowest Common Ancestor of a Binary Tree Part I | LeetCode

    VA:F [1.9.22_1171]
    0
  30. Start from root node and move downward.
    If any node found has either p or p as its direct child then it is the LCA.
    If a node is found with p in its left(or right) subtree and q in its right(or left) subtree then it is the LCA.

    For explanation and code http://www.algoqueue.com/algoqueue/default/view/8650752/find-lowest-common-ancestor-in-a-binary-tree

    VA:F [1.9.22_1171]
    0
  31. The Bottom-up method will not work if one of the nodes is not present inside the tree, I think we can use a variable for flag to represent which node have been alread found.

    VN:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.