Lowest Common Ancestor in Binary Search Tree

NeetCode: Lowest Common Ancestor in Binary Search Tree · LeetCode: 235. Lowest Common Ancestor in Binary Search Tree · Difficulty: Medium

Given a binary search tree and two nodes p and q that are both in the tree, return their lowest common ancestor: the deepest node that has both as descendants (a node counts as a descendant of itself). All values in the tree are distinct.

Example

Text

Input:  root = [5, 3, 8, 1, 4, 7, 9], p = 3, q = 8    Output: 5
Input:  root = [5, 3, 8, 1, 4, 7, 9], p = 3, q = 4    Output: 3

Trees are given in LeetCode's level-order array form: the root first, then each level from left to right, with null marking a missing node, so [1, 2, 3, 4, 5] is the tree above. The tree(Integer... values) helper in each program builds a TreeNode from such an array by filling children from a queue. TreeNode has the fields val, left, and right. A missing child is null: Java object references are nullable and the fields are mutable, so no wrapper type is needed. The examples name p and q by value. LeetCode passes them as TreeNode references, so main finds each node with a small find helper that walks the BST.

Brute force: find both root paths and compare them

Record the path from the root to each node. The LCA is the last node the two paths share. This works for any binary tree; it ignores the BST property. Nodes are compared with ==, which for objects checks that two references point to the same node.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new ArrayList<>();
        List<TreeNode> pathQ = new ArrayList<>();
        pathTo(root, p, pathP);
        pathTo(root, q, pathQ);
        TreeNode lca = root;
        for (int i = 0; i < Math.min(pathP.size(), pathQ.size()); i++) {
            if (pathP.get(i) != pathQ.get(i)) break;
            lca = pathP.get(i);
        }
        return lca;
    }

    private boolean pathTo(TreeNode node, TreeNode target, List<TreeNode> path) {
        if (node == null) return false;
        path.add(node);
        if (node == target || pathTo(node.left, target, path) || pathTo(node.right, target, path)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    static TreeNode find(TreeNode root, int val) {
        TreeNode cur = root;
        while (cur != null && cur.val != val) cur = val < cur.val ? cur.left : cur.right;
        return cur;
    }

    public static void main(String[] args) {
        TreeNode root = tree(5, 3, 8, 1, 4, 7, 9);
        System.out.println(new Solution().lowestCommonAncestor(root, find(root, 3), find(root, 8)).val);
        System.out.println(new Solution().lowestCommonAncestor(root, find(root, 3), find(root, 4)).val);
    }
}

Output

5
3

Time: O(n). Space: O(h) for the paths.

Optimal: walk down using the BST ordering

In a BST, everything left of a node is smaller and everything right is larger. Starting at the root:

If both values are smaller, the LCA is in the left subtree.
If both are larger, it is in the right subtree.
Otherwise the values are on different sides of this node (or one equals it), so this node is the LCA.

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode cur = root;
        while (cur != null) {
            if (p.val < cur.val && q.val < cur.val) {
                cur = cur.left;
            } else if (p.val > cur.val && q.val > cur.val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    static TreeNode find(TreeNode root, int val) {
        TreeNode cur = root;
        while (cur != null && cur.val != val) cur = val < cur.val ? cur.left : cur.right;
        return cur;
    }

    public static void main(String[] args) {
        TreeNode root = tree(5, 3, 8, 1, 4, 7, 9);
        System.out.println(new Solution().lowestCommonAncestor(root, find(root, 3), find(root, 8)).val);
        System.out.println(new Solution().lowestCommonAncestor(root, find(root, 3), find(root, 4)).val);
        System.out.println(new Solution().lowestCommonAncestor(root, find(root, 7), find(root, 9)).val);
    }
}

Output

5
3
8

Time: O(h), which is O(log n) for a balanced tree. Space: O(1).