[Interview Question] Find The Lowest Common Ancestor In Binary (Search) Tree (Both BT and BST)

To watch the youtube video on this topic where I explain everything, please click here.

Introduction

This series of problems asks to find the "lowest common ancestor" for two types of binary trees.

A "common ancestor" for two nodes is a node that has those two nodes as descendants (and a node can be a descendants of itself). 

The "lowest" common ancestor is the node that's closest to the two nodes that satisfies the common ancestor condition.

[Easy] Find Lowest Common Ancestor In Binary Search Tree

Given the root of a binary search tree and two nodes in the tree, p and q, find the lowest common ancestor of p and q. (Problem on Leetcode.)

For example, in the following diagram if p is node 3 and q is node 1, then the LCA(p,q) is node 2.

A binary search tree that shows the lowest common ancestor of two nodes, p and q.

---

Solution (Iterative)

We'll recognize that the node that's the LCA node of p and q must be one of the following:

1. The current node is p and q is on the left.
2. The current node is p and q is on the right.
3. The current node is q and p is on the left.
4. The current node is q and p is on the right.
5. p is on the left and q is on the right (or vice versa).

​
For this solution, we'll take advantage of the "search" property of Binary Search Trees. In a BST, a node's left children have values that are less than the node's value, and the node's right children have values that are greater than the node's value. Because of this, we'll know if the p is on the left and q is on the right without having to search those subtrees.

​The C++ solution to the problem is as follows:

The time complexity is O(N). (Specifically O(H) where H is the height of the tree.)
The space complexity is O(1) because we're not using any extra space.

Note: We choose the iterative solution here because the recursive solution has a space complexity of O(N). However, he code itself is basically the same as the iterative approach.

[Medium] Find Lowest Common Ancestor In Binary Tree

Given the root of a binary tree and two nodes in the tree, p and q, find the lowest common ancestor of p and q. (Problem on Leetcode.)

For example, in the following diagram if p is node 2 and q is node 9, then the LCA(p,q) is node 7.

A binary tree that shows the lowest common ancestor of two nodes, p and q.

---

​Solution (Recursive)

Like the previous solution, we'll recognize that the node that's the LCA node of p and q must be one of the following:

1. The current node is p and q is on the left.
2. The current node is p and q is on the right.
3. The current node is q and p is on the left.
4. The current node is q and p is on the right.
5. p is on the left and q is on the right (or vice versa).

However, this time we have a regular binary tree, and so we're forced to look through the entire tree until we find p and q. Our strategy is, for each node, recursively check the left and right subtrees to determine if either subtree has p or q in it. The node that satisfies one of these conditions is the lowest common ancestor.

The time complexity is O(N), because our recursion visits each node exactly once.
The space complexity is O(N) because  we potentially hold the entire tree in memory at the same time.

Note: We choose the recursive solution here because the code/algorithm is simpler. The iterative solution's code is harder and requires a stack.

​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake