Lowest Common Ancestor of a Binary Search Tree
Tags: leetcode, algorithms
Published: 2020-04-12 14:44:56

---
title: Lowest Common Ancestor of a Binary Search Tree
published: true
date: 2020-04-11 15:19:00 UTC
tags: LeetCode,Algorithms
canonical_url: https://coderscat.com/lowest-common-ancestor-of-a-binary-search-tree
---

In graph theory and computer science, [the lowest common ancestor (LCA)](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of two nodes is the lowest node that has both of them as descendants.

Here is an example, given a Binary Search Tree:

![CAPTURE-2020_04_11_lowest-common-ancestor-of-a-binary-search-tree.org_20200411_225813.png](https://coderscat.com/wp-content/uploads/CAPTURE-2020_04_11_lowest-common-ancestor-of-a-binary-search-tree.org_20200411_225813.png)

```
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.

```cpp
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)

```cpp
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](https://coderscat.com/lowest-common-ancestor-of-a-binary-tree).

The post [Lowest Common Ancestor of a Binary Search Tree](https://coderscat.com/lowest-common-ancestor-of-a-binary-search-tree) appeared first on [Coder's Cat](https://coderscat.com).