235. Lowest Common Ancestor of a Binary Search Tree
Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 52.1%
Problem Breakdown
The problem asks us to find the lowest common ancestor (LCA) of two given nodes in a binary search tree (BST). The LCA is defined as the lowest node that has both p and q as descendants. In a BST, for any node n, all values in its left subtree are less than n.val, and all values in its right subtree are greater than n.val.
Inputs:
- A binary search tree (BST) represented by its root node.
- Two nodes
pandqwhose LCA we need to find.
Outputs:
- The lowest common ancestor of nodes
pandq.
Implicit Constraints:
- All node values are unique.
pandqexist in the BST.p != q.
Intuition
A brute-force approach would involve finding the path from the root to both p and q, then comparing these paths to find their last common node. This approach has a time complexity of O(n) for each path traversal, where n is the number of nodes in the tree.
However, leveraging the properties of a BST can lead to a more efficient solution. Since we know that all values in the left subtree are less than the root and all values in the right subtree are greater, we can traverse the tree starting from the root and use these properties to determine where p and q lie relative to the current node.
Key Insight:
- If both
pandqare less than the current node’s value, then their LCA must be in the left subtree. - If both
pandqare greater than the current node’s value, then their LCA must be in the right subtree. - If one of
porqis equal to the current node, or if they lie on different sides of the current node, then the current node is their LCA.
Approach
- Start at the root of the BST.
- Compare the values of
p,q, and the current node:- If both
pandqare less than the current node’s value, move to the left child. - If both
pandqare greater than the current node’s value, move to the right child. - Otherwise, the current node is the LCA.
- If both
- Repeat until the LCA is found.
This approach leverages the BST properties to efficiently find the LCA with a time complexity of O(h), where h is the height of the tree.
Complexity Analysis
- Time Complexity: O(h), where h is the height of the tree. In the worst case, this can be O(n) for a skewed tree.
- Space Complexity: O(1), as we are using a constant amount of extra space.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
current = root
while current:
if p.val < current.val and q.val < current.val:
current = current.left
elif p.val > current.val and q.val > current.val:
current = current.right
else:
return current
# Example usage:
# Construct the BST from the example
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)
# Find LCA of nodes 2 and 8
print(lowestCommonAncestor(root, root.left, root.right).val) # Output: 6
# Find LCA of nodes 2 and 4
print(lowestCommonAncestor(root, root.left, root.left.right).val) # Output: 2
# Find LCA of nodes 2 and 1
print(lowestCommonAncestor(root, root.left, root.left.left).val) # Output: 2
Edge Cases Handled
- Root is one of the nodes (
porq): The algorithm correctly identifies the root as the LCA. - Nodes are on different sides of the tree: The algorithm finds the first node where the paths diverge, which is the LCA.
- Skewed Tree (worst case): Although the time complexity is O(n), the approach still works efficiently for such cases.