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

## Top comments (0)