 Coder's Cat

## Lowest Common Ancestor of a Binary Search Tree

2020-04-11

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: ## What’s Binary search tree

Binary search tree have two properties:

• The value of right child is greater than node’s value
• 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:

• current node is NULL, we will return NULL as result
• root’s value is in the range of values of `p` and `q`, root is the lowest common ancestor
• root’s value is less than `p` and `q`, then lowest common ancestor will be in the left subtree
• 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.

## 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)

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.

Join my Email List for more helpful insights, It's Free!😋