Log inSign up
mediumLeetCodeNot Started

Lowest Common Ancestor of a Binary Search Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

Given a Binary Search Tree (BST), find the lowest common ancestor (LCA) node of two given nodes p and q in the BST.

According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Contrast generic binary tree LCA (O(N)) with BST LCA (O(H)).
  • Identify the split-point invariant in BST branching.
  • Implement the O(1) space iterative descent.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • LCA query on Binary Search Tree (not generic binary tree).
  • Take advantage of BST ordering to avoid full tree recursion.
  • Split point navigation.

Algorithmic Decision Tree:

  • Both p, q < curr: go left.
  • Both p, q > curr: go right.
  • One <= curr and other >= curr: curr is LCA.

Connected Patterns:

Lowest Common Ancestor of a Binary TreeSearch in a Binary Search TreeValidate Binary Search Tree

1. Root-to-Node Path Intersection

Intuition

Perform standard BST searches from root to p and from root to q, storing the visited nodes in paths pathP and pathQ. Iterate through both lists simultaneously from index 0 until the nodes diverge. The last matching node is the LCA. Takes O(H) time and O(H) auxiliary space to store paths.

When to apply: When path reconstruction is explicitly required for tracing or debugging.

Algorithm

  1. Find path from root to p, and path from root to q using BST search. The last common node in both paths is the LCA.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 bool getPath(TreeNode* root, TreeNode* target, std::vector<TreeNode*>& path) {
13 TreeNode* curr = root;
14 while (curr) {
15 path.push_back(curr);
16 if (target->val < curr->val) curr = curr->left;
17 else if (target->val > curr->val) curr = curr->right;
18 else return true;
19 }
20 return false;
21 }
22public:
23 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
24 std::vector<TreeNode*> pathP, pathQ;
25 getPath(root, p, pathP);
26 getPath(root, q, pathQ);
27
28 TreeNode* lca = nullptr;
29 int n = std::min(pathP.size(), pathQ.size());
30 for (int i = 0; i < n; i++) {
31 if (pathP[i] == pathQ[i]) lca = pathP[i];
32 else break;
33 }
34 return lca;
35 }
36};
37
38int main() {
39 TreeNode* root = new TreeNode(6);
40 root->left = new TreeNode(2);
41 root->right = new TreeNode(8);
42 root->left->left = new TreeNode(0);
43 root->left->right = new TreeNode(4);
44 root->left->right->left = new TreeNode(3);
45 root->left->right->right = new TreeNode(5);
46 root->right->left = new TreeNode(7);
47 root->right->right = new TreeNode(9);
48
49 Solution sol;
50 TreeNode* ans = sol.lowestCommonAncestor(root, root->left, root->right);
51 std::cout << "LCA of 2 and 8: " << ans->val << std::endl;
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(H) to store paths

2. Recursive BST Split-Point Descent

Intuition

1. If p.val < root.val and q.val < root.val, return lowestCommonAncestor(root.left, p, q). 2. If p.val > root.val and q.val > root.val, return lowestCommonAncestor(root.right, p, q). 3. Otherwise, root is the split point where paths diverge. Return root.

When to apply: Concise recursive solution for technical interviews.

Algorithm

  1. Recurse down left if both < curr.val; recurse right if both > curr.val; otherwise return curr.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
13 if (!root) return nullptr;
14
15 if (p->val < root->val && q->val < root->val) {
16 return lowestCommonAncestor(root->left, p, q);
17 }
18 if (p->val > root->val && q->val > root->val) {
19 return lowestCommonAncestor(root->right, p, q);
20 }
21
22 return root;
23 }
24};
25
26int main() {
27 TreeNode* root = new TreeNode(6);
28 root->left = new TreeNode(2);
29 root->right = new TreeNode(8);
30 root->left->left = new TreeNode(0);
31 root->left->right = new TreeNode(4);
32 root->left->right->left = new TreeNode(3);
33 root->left->right->right = new TreeNode(5);
34 root->right->left = new TreeNode(7);
35 root->right->right = new TreeNode(9);
36
37 Solution sol;
38 TreeNode* ans = sol.lowestCommonAncestor(root, root->left, root->right);
39 std::cout << "LCA of 2 and 8: " << ans->val << std::endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(H) recursion stack space

3. Iterative Split-Point Descent (O(1) Auxiliary Space)

Intuition

1. Start curr = root. 2. While curr != null: - If p.val < curr.val && q.val < curr.val, move curr = curr.left. - If p.val > curr.val && q.val > curr.val, move curr = curr.right. - Else, return curr. Zero recursion stack overhead, strictly O(1) auxiliary space.

When to apply: Optimal in both time and space. Industry standard for production systems.

Algorithm

  1. Descend tree iteratively with a single while loop. Return current node the moment p and q values diverge.

BST LCA Split-Point Traversal Trace

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Move curr = curr
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
curr = 6: p.val (2) < 6 and q.val (4) < 6 -> Both in left subtree.
Decision / next transition
1
Why this step matters

Move curr = curr.left (2).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
13 TreeNode* curr = root;
14 while (curr) {
15 if (p->val < curr->val && q->val < curr->val) {
16 curr = curr->left;
17 } else if (p->val > curr->val && q->val > curr->val) {
18 curr = curr->right;
19 } else {
20 return curr;
21 }
22 }
23 return nullptr;
24 }
25};
26
27int main() {
28 TreeNode* root = new TreeNode(6);
29 root->left = new TreeNode(2);
30 root->right = new TreeNode(8);
31 root->left->left = new TreeNode(0);
32 root->left->right = new TreeNode(4);
33 root->left->right->left = new TreeNode(3);
34 root->left->right->right = new TreeNode(5);
35 root->right->left = new TreeNode(7);
36 root->right->right = new TreeNode(9);
37
38 Solution sol;
39 TreeNode* ans = sol.lowestCommonAncestor(root, root->left, root->left->right); // LCA(2, 4)
40 std::cout << "LCA of 2 and 4: " << ans->val << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Root-to-Node Path IntersectionO(H) where H is tree heightO(H) to store pathsFind path from root to p, and path from root to q using BST search. The last common node in both paths is the LCA.O(H) where H is tree height
2.Recursive BST Split-Point DescentO(H) where H is tree heightO(H) recursion stack spaceRecurse down left if both < curr.val; recurse right if both > curr.val; otherwise return curr.O(H) where H is tree height
3.Iterative Split-Point Descent (O(1) Auxiliary Space)OptimalO(H) where H is tree heightO(1) auxiliary spaceDescend tree iteratively with a single while loop. Return current node the moment p and q values diverge.O(H) where H is tree height

Common Pitfalls & Crucial Edge Cases

Assuming p.val is always less than q.val

Hardcoding p.val < curr.val < q.val fails if input gives p.val > q.val.

Using generic binary tree LCA

Visits all N nodes instead of following the O(H) BST path.

Checking values with wrong signs

Integer overflow if computing difference (p.val - curr.val) * (q.val - curr.val).

Crucial Edge Cases to Validate:

  • p is the direct ancestor of q — Node p is returned as the LCA.
  • p and q are the root and a leaf — Returns the root.
  • p and q are immediate left and right children of root — Returns root in 1 step.
  • Large BST of height 10^5 — Iterative descent runs without stack overflow.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the split-point insight immediately: 'LCA in a BST is simply the divergence node where p and q split into left and right branches.'
  2. Mention that the solution requires no assumption about which node is smaller.
  3. Highlight the O(1) auxiliary space of the iterative while-loop.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the first node where paths to p and q diverge guarantee to be the LCA?

2.What is the space complexity of the iterative BST LCA algorithm?

3.What if one of the target nodes p is an ancestor of q in the BST?

Back to DSA Sheet