CodingGyan

Lowest Common Ancestor in a BST

medium Data Structures and Algorithms

Problem

The first line has distinct numbers. Insert them one by one into an empty binary search tree (smaller numbers go left, bigger numbers go right). The second line has two numbers p and q that are in the tree. Print the value of their lowest common ancestor: the deepest node that has both p and q below it (a node counts as below itself). Use the BST order, not a search for both nodes.

Constraints

  • 1 <= n <= 1000
  • values are distinct
  • p and q are in the tree

Examples

Input

6 2 8 0 4 7 9
2 8

Output

6

Solutions

Best approachTime O(n * h)Space O(n)

In a BST the order of the values tells where both nodes are, so no search in both subtrees is needed. The answer is the first node on the way down whose value lies between p and q. The time is O(h), the height of the tree.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process a tree.
 * Input   : Line 1: values to insert. Line 2: the query.
 * Output  : The LCA value.
 * Approach: Build a BST, then walk down.
 * Time    : O(n * h)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A node holds a value and two children. Smaller values go to the left, bigger values go to the right.
        static class Node {
            final long value;
            Node left;
            Node right;

            Node(long value) {
                this.value = value;
            }
        }

        static Node insert(Node root, long value) {
            if (root == null) {
                return new Node(value);
            }
            if (value < root.value) {
                root.left = insert(root.left, value);
            } else {
                root.right = insert(root.right, value);
            }
            return root;
        }

    // This method solves the task. It receives the input and returns the answer.
    static long solve(String[] lines) {
        Node root = null;
        for (String text : lines[0].split(" ")) {
            root = insert(root, Long.parseLong(text));
        }
        String[] query = lines[1].split(" ");
        long first = Long.parseLong(query[0]);
        long second = Long.parseLong(query[1]);
        // Step 2: Walk down from the root. If both values are smaller, go left. If both are bigger, go right.
        Node current = root;
        while (true) {
            if (Math.max(first, second) < current.value) {
                current = current.left;
            } else if (Math.min(first, second) > current.value) {
                current = current.right;
            } else {
                // Step 3: The values are on different sides (or one equals this node). This node is the answer.
                return current.value;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(solve(lines));
    }
}
Hints (1)
  1. Why is the answer the first node with p <= value <= q?

Try these next