# LeetCode 235: Lowest Common Ancestor of a Binary Search Tree ## Problem Restatement We are given: - The `root` of a binary search tree - Two nodes `p` and `q` We need to find their lowest common ancestor. The lowest common ancestor, usually called LCA, is the lowest node in the tree such that both `p` and `q` are descendants of that node. A node may be a descendant of itself. LeetCode examples include: ```text Input: root = [6,2,8,0,4,7,9,null,null,3,5] p = 2 q = 8 Output: 6 ``` and: ```text Input: root = [6,2,8,0,4,7,9,null,null,3,5] p = 2 q = 4 Output: 2 ``` The tree contains unique values, and both `p` and `q` exist in the BST. ([leetcode.com](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/?utm_source=chatgpt.com)) ## Input and Output | Item | Meaning | |---|---| | Input | BST root, node `p`, node `q` | | Output | The lowest common ancestor node | | BST property | Left values < root < right values | | Guarantee | `p` and `q` exist in the tree | Tree node shape: ```python class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None ``` Function shape: ```python class Solution: def lowestCommonAncestor( self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode' ) -> 'TreeNode': ... ``` ## Examples Example 1: ```text Tree: 6 / \ 2 8 / \ / \ 0 4 7 9 / \ 3 5 p = 2 q = 8 ``` The answer is: ```text 6 ``` because: - `2` is in the left subtree of `6` - `8` is in the right subtree of `6` So `6` is the first node where the paths split. Example 2: ```text p = 2 q = 4 ``` The answer is: ```text 2 ``` because: - `2` is an ancestor of `4` - A node can be an ancestor of itself So the lowest common ancestor is `2`. ## First Thought: Store Paths One possible method is: 1. Find the path from root to `p` 2. Find the path from root to `q` 3. Compare the paths 4. The last common node is the LCA This works for any binary tree. But here we have a binary search tree, which gives much stronger structure. We can solve the problem without storing paths. ## Key Insight A binary search tree satisfies: ```text all left subtree values < root value all right subtree values > root value ``` So the relative positions of `p` and `q` determine where the LCA must be. There are only three possibilities. ## Case 1: Both Nodes Are Smaller Suppose: ```text p.val < root.val q.val < root.val ``` Then both nodes are in the left subtree. So the LCA must also be in the left subtree. We move left. ## Case 2: Both Nodes Are Larger Suppose: ```text p.val > root.val q.val > root.val ``` Then both nodes are in the right subtree. So the LCA must also be in the right subtree. We move right. ## Case 3: The Nodes Split Suppose: ```text p.val < root.val < q.val ``` or: ```text q.val < root.val < p.val ``` Then one node is on each side. That means the current root is exactly the first point where the paths diverge. So the current root is the LCA. This also covers the case where one node equals the root. ## Visual Example Consider: ```text 6 / \ 2 8 / \ / \ 0 4 7 9 ``` Find LCA of: ```text 2 and 8 ``` At root `6`: ```text 2 < 6 8 > 6 ``` The nodes split around `6`. So: ```text LCA = 6 ``` Now find LCA of: ```text 2 and 4 ``` At root `6`: ```text 2 < 6 4 < 6 ``` Both are left. Move left to `2`. Now: ```text p = 2 q = 4 root = 2 ``` One node equals the current root. So: ```text LCA = 2 ``` ## Algorithm Start at the root. Repeatedly: 1. If both `p` and `q` are smaller than the current node: - Move left 2. Else if both are larger: - Move right 3. Otherwise: - Return the current node The loop stops as soon as the nodes split or match the current node. ## Correctness At every step, the BST ordering property guarantees that: - All smaller values lie entirely in the left subtree - All larger values lie entirely in the right subtree If both `p` and `q` are smaller than the current node, then every common ancestor must lie in the left subtree. Moving left preserves the correct answer. Similarly, if both are larger, every common ancestor must lie in the right subtree. Moving right preserves the correct answer. Eventually, one of two things happens: 1. The nodes lie on different sides of the current node. 2. One node equals the current node. In either case, the current node is the first node whose subtree contains both `p` and `q`. Therefore, the current node is their lowest common ancestor. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(h)` | We move downward once | | Space | `O(1)` | Iterative solution uses constant memory | Here, `h` is the height of the tree. For a balanced BST: ```text h = O(log n) ``` For a skewed BST: ```text h = O(n) ``` ## Implementation ```python class Solution: def lowestCommonAncestor( self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode' ) -> 'TreeNode': while root: if p.val < root.val and q.val < root.val: root = root.left elif p.val > root.val and q.val > root.val: root = root.right else: return root ``` ## Code Explanation We start at the root: ```python while root: ``` If both target values are smaller: ```python if p.val < root.val and q.val < root.val: root = root.left ``` then both nodes must be in the left subtree. If both target values are larger: ```python elif p.val > root.val and q.val > root.val: root = root.right ``` then both nodes must be in the right subtree. Otherwise: ```python return root ``` This means: - the nodes split across the current node, or - one node equals the current node In both situations, the current node is the lowest common ancestor. ## Recursive Version The same logic can be written recursively. ```python class Solution: def lowestCommonAncestor( self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode' ) -> 'TreeNode': if p.val < root.val and q.val < root.val: return self.lowestCommonAncestor(root.left, p, q) if p.val > root.val and q.val > root.val: return self.lowestCommonAncestor(root.right, p, q) return root ``` The iterative version avoids recursion stack usage, so it uses constant extra space. ## Testing ```python from collections import deque class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def build_tree(values): if not values: return None root = TreeNode(values[0]) q = deque([root]) i = 1 while q and i < len(values): node = q.popleft() if i < len(values) and values[i] is not None: node.left = TreeNode(values[i]) q.append(node.left) i += 1 if i < len(values) and values[i] is not None: node.right = TreeNode(values[i]) q.append(node.right) i += 1 return root def find_node(root, value): if root is None: return None if root.val == value: return root if value < root.val: return find_node(root.left, value) return find_node(root.right, value) ``` ```python def run_tests(): s = Solution() root = build_tree([6,2,8,0,4,7,9,None,None,3,5]) p = find_node(root, 2) q = find_node(root, 8) assert s.lowestCommonAncestor(root, p, q).val == 6 p = find_node(root, 2) q = find_node(root, 4) assert s.lowestCommonAncestor(root, p, q).val == 2 p = find_node(root, 3) q = find_node(root, 5) assert s.lowestCommonAncestor(root, p, q).val == 4 root = build_tree([2,1]) p = find_node(root, 2) q = find_node(root, 1) assert s.lowestCommonAncestor(root, p, q).val == 2 print("all tests passed") run_tests() ``` | Test | Why | |---|---| | `2` and `8` | Nodes split at root | | `2` and `4` | One node is ancestor | | `3` and `5` | LCA inside subtree | | Small tree | Minimal nontrivial BST |