Lowest Common Ancestor of a Binary Search Tree
Walk down — go right if both values exceed node, left if both are less; otherwise current is the LCA.
3 min read
tree bst
Problem#
Given a BST and two values p and q (both present), return their lowest common ancestor.
Examples#
root=[6,2,8,0,4,7,9,null,null,3,5], p=2, q=8→6.root=[6,2,8,0,4,7,9,null,null,3,5], p=2, q=4→2.
Constraints#
- All node values are unique.
Approach#
If both p and q are greater than the current node, recurse right; if both less, recurse left; otherwise the current node is the LCA.
Solution#
struct TreeNode { int val; TreeNode* left; TreeNode* right; };
class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while (root) { if (p->val > root->val && q->val > root->val) root = root->right; else if (p->val < root->val && q->val < root->val) root = root->left; else return root; } return nullptr; }};func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { for root != nil { if p.Val > root.Val && q.Val > root.Val { root = root.Right } else if p.Val < root.Val && q.Val < root.Val { root = root.Left } else { return root } } return nil}from typing import Optional
class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> Optional['TreeNode']: while root: if p.val > root.val and q.val > root.val: root = root.right elif p.val < root.val and q.val < root.val: root = root.left else: return root return Nonefunction lowestCommonAncestor(root, p, q) { while (root) { if (p.val > root.val && q.val > root.val) root = root.right; else if (p.val < root.val && q.val < root.val) root = root.left; else return root; } return null;}class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (root != null) { if (p.val > root.val && q.val > root.val) root = root.right; else if (p.val < root.val && q.val < root.val) root = root.left; else return root; } return null; }}function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null { 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;}Editorial#
The BST property fully determines the LCA’s location: it’s the first node where p and q straddle (one on each side, or one equals it). Iterative walk is O(1) space, ideal here.
Complexity#
- Time:
O(h). - Space:
O(1).
Concept revision#
Related#