Lowest Common Ancestor in Binary Search Tree
Lowest Common Ancestor of a Binary Search Tree Problem
Given a binary search tree (BST) with unique node values and two nodes p and q, return their lowest common ancestor (LCA).
The LCA is the lowest node in the tree such that both p and q are its descendants. A node can also be considered as its own descendant.
Example 1:
Illustration 1:
Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 8
Output: 5
Output: 5
Example 2:
Illustration 2:
Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 4
Output: 3
LCA of nodes 3 and 4 is 3 , because a node can be a descendant of itself.
Output: 3
LCA of nodes 3 and 4 is 3 , because a node can be a descendant of itself.
Constraints:
- 2 <= Number of nodes in the tree <= 100.
- -100 <= Node.val <= 100
- p != q
- p and q will both exist in the BST.
Hints to Solve Lowest Common Ancestor of a Binary Search Tree
Recommendation for Time and Space Complexity:
Aim for a solution with a time complexity of O(h) and a space complexity of O(h) or better, where h is the height of the tree.
Hint 1 :
- Binary Search Tree (BST) follows the property where all nodes in the left subtree are smaller than the current node, and all nodes in the right subtree are greater.
- This property holds for every node in the tree.
- The Question is – Can you leverage this rule to identify the Lowest Common Ancestor (LCA) of the given nodes?
Hint 2 :
- Use recursion to traverse the tree. Think about the conditions where you decide to move left or right in the tree based on the values of the two nodes.
- How can these conditions help pinpoint the LCA?
Hint 3 :
- When the two nodes lie in different subtrees, the current node becomes the LCA because a split occurs.
- If both nodes are in the left or right subtree, the LCA must be there, so you continue traversing in that direction.
Hint 4 :
- If the current node matches one of the given nodes p or q, it is the LCA.
- This is because encountering p or q during the traversal automatically makes that node the lowest ancestor.
There are mainly 2 approach to solve this problem:
- Recursion Method
- Iteration Method
1. Recursion Method
Use the BST property to traverse the tree recursively. At each step, decide whether to move left, right, or return the current node as the LCA based on the values of p and q.
- Time complexity: O(h)
- Space complexity: O(h)
where h is height of the tree.
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || !p || !q) {
return nullptr;
}
if (max(p->val, q->val) < root->val) {
return lowestCommonAncestor(root->left, p, q);
} else if (min(p->val, q->val) > root->val) {
return lowestCommonAncestor(root->right, p, q);
} else {
return root;
}
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) {
return null;
}
if (Math.max(p.val, q.val) < root.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (Math.min(p.val, q.val) > root.val) {
return lowestCommonAncestor(root.right, p, q);
} else {
return root;
}
}
}
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or not p or not q:
return None
if (max(p.val, q.val) < root.val):
return self.lowestCommonAncestor(root.left, p, q)
elif (min(p.val, q.val) > root.val):
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
lowestCommonAncestor(root, p, q) {
if (!root || !p || !q) {
return null;
}
if (Math.max(p.val, q.val) < root.val) {
return this.lowestCommonAncestor(root.left, p, q);
} else if (Math.min(p.val, q.val) > root.val) {
return this.lowestCommonAncestor(root.right, p, q);
} else {
return root;
}
}
}
2. Iteration Method
Instead of recursion, use a loop to traverse the tree. At each node, check the values of p and q to determine the direction (left, right, or current node) until the LCA is found.
- Time complexity: O(h)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* cur = root;
while (cur) {
if (p->val > cur->val && q->val > cur->val) {
cur = cur->right;
} else if (p->val < cur->val && q->val < cur->val) {
cur = cur->left;
} else {
return cur;
}
}
return nullptr;
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode cur = root;
while (cur != null) {
if (p.val > cur.val && q.val > cur.val) {
cur = cur.right;
} else if (p.val < cur.val && q.val < cur.val) {
cur = cur.left;
} else {
return cur;
}
}
return null;
}
}
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
cur = root
while cur:
if p.val > cur.val and q.val > cur.val:
cur = cur.right
elif p.val < cur.val and q.val < cur.val:
cur = cur.left
else:
return cur
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
lowestCommonAncestor(root, p, q) {
let cur = root;
while (cur) {
if (p.val > cur.val && q.val > cur.val) {
cur = cur.right;
} else if (p.val < cur.val && q.val < cur.val) {
cur = cur.left;
} else {
return cur;
}
}
return null;
}
}
