Lowest Common Ancestor of a Binary Search Tree

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes is the lowest node that has both of them as descendants.

Here is an example, given a Binary Search Tree:

LCA(2, 8) = 6 LCA(4, 7) = 6LCA(2, 5) = 2LCA(0, 3) = 2

What’s Binary search tree

Binary search tree has two properties:

1. The value of right child is greater than node’s value
2. The value of left child is less than node’s value

Approach #1: Recursive Algorithm

If we traverse each node of binary search tree and comparing the values of p, q and current node’s value, there are four scenarios:

1. current node is NULL, we will return NULL as result
2. root’s value is in the range of values of p and q, root is the lowest common ancestor
3. root’s value is less than p and q, then lowest common ancestor will be in the left subtree
4. root’s value is greater than p and q, then the lowest common ancestor will be the right subtree.

Time Complexity: O(N)

Space Complexity: O(N) for recursion stack.

class Solution {
public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root == NULL || p == NULL || q == NULL)
      return NULL; // scenario #1
    if((p->val <= root->val && root->val <= q->val) ||
       (p->val >= root->val && root->val >= q->val))
      return root; // scenario #2
    if(p->val < root->val && q->val < root->val) {
      return lowestCommonAncestor(root->left, p, q); // scenario #3 
    }
    if(p->val > root->val && q->val > root->val) {
      return lowestCommonAncestor(root->right, p, q); // scenario #4
    }
    return NULL;
  }
};

Approach #2: Iterative Algorithm

Iterative algorithm works similarly to the recursive algorithm, but we don’t need a stack to backtrace search. In fact, we only need to find the first node, which p and q begin to split, one of them is in this node’s left subtree, and the other is in the right subtree.

This algorithm is somehow similar to binary search.

Time Complexity: O(N)

Space Complexity: O(1)

class Solution {
public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* node = root;
    while(node != NULL) { 
        if(node->val > p->val && node->val > q->val) 
            node = node->left;
        else if(node->val < p->val && node->val < q->val)
            node = node->right;
        else
            return node;
    }
    return NULL;     
  }
};

When the tree is not a binary search tree, but only a binary tree. The solution would be more complex. Please refer to Lowest Common Ancestor Of A Binary Tree.

The post Lowest Common Ancestor of a Binary Search Tree appeared first on Coder's Cat.