Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. In a BST you always know which side a value lives on.
  2. 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