Practice › Trees
Lowest Common Ancestor in a BST
Medium · Trees · Asked at Amazon, Microsoft, Google, Meta
A BST is built by inserting the given distinct values in the given order into an empty tree. Print the value of the lowest common ancestor of nodes p and q.
Input
First line: n. Second line: n distinct values (insertion order). Third line: p q (both present).
Output
The LCA value.
Constraints
- 1 ≤ n ≤ 10^4
From the root: if both are smaller go left, if both are larger go right, otherwise this node is the LCA.
Example 1
Input
9 6 2 8 0 4 7 9 3 5 2 8
Output
6
Example 2
Input
9 6 2 8 0 4 7 9 3 5 2 4
Output
2
Hints
- In a BST you always know which side a value lives on.
- From the root: if p and q are both smaller, go left; both larger, go right; otherwise they split here — this node is the LCA.
Approach
Insert the values in the given order to build the BST, iteratively so a sorted input can't overflow the stack. Then walk from the root. While both p and q are less than the current value, go left. While both are greater, go right. The first node where they fall on different sides, or where one of them equals the node, is their lowest common ancestor.
Complexity: O(n · h) to build, O(h) to answer · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
int main() {
int n;
cin >> n;
Node *root = nullptr;
for (int i = 0; i < n; i++) {
long long v;
cin >> v;
Node **slot = &root; // walk down to the empty spot for v
while (*slot) slot = v < (*slot)->val ? &(*slot)->left : &(*slot)->right;
*slot = new Node(v);
}
long long p, q;
cin >> p >> q;
Node *cur = root;
while (true) {
if (p < cur->val && q < cur->val) cur = cur->left;
else if (p > cur->val && q > cur->val) cur = cur->right;
else break;
}
cout << cur->val << "\n";
return 0;
}Python solution
import sys
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
data = list(map(int, sys.stdin.read().split()))
n = data[0]
root = None
for v in data[1 : n + 1]:
if root is None:
root = Node(v)
continue
cur = root
while True: # walk down to the empty spot for v
if v < cur.val:
if cur.left is None:
cur.left = Node(v)
break
cur = cur.left
else:
if cur.right is None:
cur.right = Node(v)
break
cur = cur.right
p, q = data[n + 1], data[n + 2]
cur = root
while True:
if p < cur.val and q < cur.val:
cur = cur.left
elif p > cur.val and q > cur.val:
cur = cur.right
else:
break
print(cur.val)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node root = null;
for (int i = 0; i < n; i++) {
long v = sc.nextLong();
if (root == null) { root = new Node(v); continue; }
Node cur = root;
while (true) { // walk down to the empty spot for v
if (v < cur.val) {
if (cur.left == null) { cur.left = new Node(v); break; }
cur = cur.left;
} else {
if (cur.right == null) { cur.right = new Node(v); break; }
cur = cur.right;
}
}
}
long p = sc.nextLong(), q = sc.nextLong();
Node cur = root;
while (true) {
if (p < cur.val && q < cur.val) cur = cur.left;
else if (p > cur.val && q > cur.val) cur = cur.right;
else break;
}
System.out.println(cur.val);
}
}Solve Lowest Common Ancestor in a BST online · All practice problems