# Lowest Common Ancestor of a Binary Search Tree Leetcode Solution

Difficulty Level Easy
Binary Search Tree Huawei Reddit Tree WalmartViews 88

## Problem Statement:

Lowest Common Ancestor of a Binary Search Tree Leetcode Solution – Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

Note: “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).”

## Example:

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

## Approach:

### Iterate in BST

1. Calculate the maximum between the value of node p and node q and store the value in maxi, and in the same way, calculate the minimum between the value of node p and node q and store the value in mini.
2. We keep iterating root in BST and check :
1. If  `the value of root node > maxi` then both node `p` and `q` belong to the left subtree, go to the left of the tree.
2. If  `the value of root node``< mini` then both node `p` and `q` belong to the right subtree, go to the right of the tree.
3. Now, `mini <= the value of root node <= maxi` the current `root` is the LCA between `q` and `p`.   ## Code:

### C++ Program of  Lowest Common Ancestor of a Binary Search Tree:

```class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
int mini = min(p->val, q->val);
int maxi = max(p->val, q->val);
while (root != nullptr) {
if (root->val > maxi)
root = root->left;
else if (root->val < mini)
root = root->right;
else
return root;
}
return nullptr;

}
};```

### Java Program of  Lowest Common Ancestor of a Binary Search Tree:

```class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int mini = Math.min(p.val, q.val);
int maxi = Math.max(p.val, q.val);
while (root != null) {
if (root.val > maxi)
root = root.left;
else if (root.val < mini)
root = root.right;
else
return root;
}
return null;
}
}```

## Complexity Analysis for Lowest Common Ancestor of a Binary Search Tree Leetcode Solution:

### Time Complexity:

The Time Complexity of the code is O(H), where H is the height of the Binary Tree.

### Space Complexity:

The Space Complexity of the code is O(1) because we don’t need any extra space to solve this problem.

Translate »