Lowest Common Ancestor of a BST
Find the lowest common ancestor of two nodes in a binary search tree with distinct values. Both nodes exist; a node may be its own ancestor.
Work through the cases
3 examplesInput notation
A binary tree in level order on one line, using null for missing children. Omit trailing nulls; use null for an empty tree. Line 2 contains the two target values.Expected result
The ancestor value.Case 1
Input
6 2 8 0 4 7 9 0 4
Expected output
2
Case 2
Input
6 2 8 2 8
Expected output
6
Case 3
Input
2 1 3 1 2
Expected output
2
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
In a BST the LCA of p and q is the fork between their values. Walk from the root: go left if both are smaller, right if both are larger, otherwise the current node is the fork. The walk is iterative and needs no call stack.
Starting from the root node, we traverse the tree. If the current node's value is less than both p and q values, it means that p and q should be in the right subtree of the current node, so we move to the right child. If the current node's value is greater than both p and q values, it means that p and q should be in the left subtree, so we move to the left child. Otherwise, it means the current node is the lowest common ancestor of p and q, so we return the current node.
The time complexity is O(n), where n is the number of nodes in the binary search tree. The space complexity is O(1).
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (true) {
if (root.val < Math.min(p.val, q.val)) {
root = root.right;
} else if (root.val > Math.max(p.val, q.val)) {
root = root.left;
} else {
return root;
}
}
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.