We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Binary Search Tree : Lowest Common Ancestor
  2. Discussions

Binary Search Tree : Lowest Common Ancestor

Sort by

recency

|

36 Discussions

|

  • thomhickey
     + 1 comment

    Example BST is not a BST, right child of 2 should be 4, not 3. Please fix this confusion! Correct example for 1,2,3,4,5,6 with 2 as root is follows, which means LCA for 4 and 6 would be 2:

       2
  / \
 1   4
    / \
   3   5
         \
          6

  • fencullen
     + 0 comments

    C++

    Node* lca(Node* root, int a, int b) 
{
    // LCA is the node on which the search for a and b diverges. Either split left and right or found a or b.
    
    while(true)
    {
        if (a > root->data && b > root->data)
        {
            root = root->right;
        }
        else if (a < root->data && b < root->data) 
        {
            root = root->left;
        }
        else {
            return root;
        }
    }
}

  • 1337er
     + 0 comments
    def get_chain(root, val, chain):
    if not root:
        return None
    if root.info == val:
        chain = chain + (root,)
        return chain
    left_result = get_chain(root.left, val, chain)
    if left_result:
        return left_result + (root,)
    right_result = get_chain(root.right, val, chain)
    if right_result:
        return right_result + (root,)
    return chain


def lca(root, v1, v2):
    x = get_chain(root, v1, ())
    y = get_chain(root, v2, ())
    x = list(x)
    y = set(y)
    common = None
    for i in range(len(x)):
        if x[-(i+1)] in y:
            common = x[-(i+1)]
    return common

  • yashdeora98294
     + 0 comments

    Here is Hackerrank binary search tree lowest common ancestor problem solution in python java c++ c and javascript

  • vgambit
     + 0 comments

    The first example given is NOT a binary search tree. HackerRank, please fix it. It is confusing.