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

  • 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;
        }
    }
}