## DEV Community

Posted on • Originally published at alkeshghorpade.me

# LeetCode - Lowest Common Ancestor of a Binary Search Tree

### Problem statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: The lowest common ancestor is defined between two nodes `p` and `q` as the lowest node in `T` that has both `p` and `q` as descendants (where we allow a node to be a descendant of itself).

Problem statement taken from: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Example 1:

``````Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
``````

Example 2:

``````Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
``````

Example 3:

``````Input: root = [2, 1], p = 2, q = 1
Output: 2
``````

Constraints:

``````- The number of nodes in the tree is in the range [2, 10^5]
- -10^9 <= Node.val <= 10^9
- All Node.val are unique
- p != q
- p and q will exist in the BST
``````

### Explanation

#### Storing paths

The solution in this approach is to store the path from the root to p and root to q in two separate arrays. We then find the first element in the arrays that are mismatched.

For Example 2:

The path from the root to 2: [6, 2]

The path from the root to 4: [6, 2, 4]

We find the first element: 6 matches. We check the next element, which is 2, and it matches. The array for path root to 2 is done, and the array for path root to 4 has an element at the 2nd index; we consider it a mismatch.

We return the last element in both the arrays that match, which is 2.

A C++ snippet of the above approach is as follows:

``````bool findPath(Node* root, vector<int>& path, int k) {
if (root == NULL) {
return false;
}

path.push_back(root->val);

if (root->val == k) {
return true;
}

if ((root->left && findPath(root->left, path, k))
|| (root->right && findPath(root->right, path, k))) {
return true;
}

path.pop_back();
return false;
}

int findLCA(Node* root, int p, int q) {
vector<int> path1, path2;
int i;

if (!findPath(root, path1, p)
|| !findPath(root, path2, q)) {
return -1;
}

for (i = 0; i < path1.size() && i < path2.size(); i++)
if (path1[i] != path2[i])
break;

return path1[i - 1];
}
``````

The time complexity and the space complexity of the above approach is O(n).

#### Single Traversal

We use preorder traversal and solve the problem using below steps:

• We check if the value of the root matches p and q
• If yes, we return the root
• else we recursively call the left and right subtree
• If there is any root that returns one NULL and one NON-NULL value, we return the corresponding NON-NULL value for that node.
• The root that returns both NON-NULL values for both the left and right subtree, is our LCA.

A C++ snippet of the above approach is as follows:

``````struct Node* findLCA(struct Node* root, int p, int q) {
if (root == NULL)
return NULL;

if (root->key == p || root->key == q)
return root;

Node* leftLCA = findLCA(root->left, p, q);
Node* rightLCA = findLCA(root->right, p, q);

if (leftLCA && rightLCA) {
return root;
}

return (leftLCA != NULL) ? leftLCA : rightLCA;
}
``````

The time complexity of the above approach is O(n), and the space complexity is O(h), where h is the tree's height.

#### Recursion

The problem statement states that the tree is a Binary Search Tree (BST). We can modify the above recursive approach to avoid unnecessary calls to the left and right subtree.

Let's check the algorithm first.

``````- if root == null
- return null

- if root->val > p->val && root->val > q->val
- return lca(root->left, p, q)

- if root->val < p->val && root->val < q->val
- return lca(root->right, p, q)

- return root
``````

This approach's time and space complexity are O(h), where h is the tree's height.

Let's check our algorithm in C++, Golang, and JavaScript.

#### C++ solution

``````class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL) {
return NULL;
}

if(root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
}

if(root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q);
}

return root;
}
};
``````

#### Golang solution

``````func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil {
return nil
}

if root.Val > p.Val && root.Val > q.Val {
return lowestCommonAncestor(root.Left, p, q)
}

if root.Val < p.Val && root.Val < q.Val {
return lowestCommonAncestor(root.Right, p, q)
}

return root
}
``````

#### JavaScript solution

``````var lowestCommonAncestor = function(root, p, q) {
if(root === null) {
return null;
}

if(root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}

if(root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}

return root;
};
``````

Let's dry-run our algorithm to see how the solution works.

``````Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
p = 2
q = 4

Step 1: if root == NULL
root -> 6
false

if root->val > p->val && root->val > q->val
6 > 2 && 6 > 4
true

return lowestCommonAncestor(root->left, p, q)
lowestCommonAncestor(->2, ->2, ->4)

// lowestCommonAncestor(->2, ->2, ->4)
Step 2: if root == NULL
root -> 2
false

if root->val > p->val && root->val > q->val
2 > 2 && 2 > 4
false

if root->val < p->val && root->val < q->val
2 < 2 && 2 < 4
false

return root

We backtrack to Step 1

Step 3: return lowestCommonAncestor(root->left, p, q)
lowestCommonAncestor(->2, ->2, ->4)
2

We return the answer as 2.
``````