Lowest Common Ancestor in a BST

Time: O(h)

Space: O(1)

Intuition

BST property: LCA is the first node where paths to n1 and n2 diverge. If both values are less than current node, LCA is in left subtree; if both greater, in right; else current is LCA.

Algorithm

1While root != null:
2If n1 < root.val and n2 < root.val: root = root.left.
3If n1 > root.val and n2 > root.val: root = root.right.
4Else return root.

Common Pitfalls

•Only valid for BST. For general binary tree, use the standard LCA algorithm.

Lowest Common Ancestor in a BST.java

Java

// Approach: BST property: if both nodes < root go left; if both > root go right; else root is LCA.
// Time: O(h) Space: O(1)
class Node {
    int data;
    Node left, right;

    public Node(int d) {
        data = d;
        left = right = null;
    }
}

class Solution {
    Node LCA(Node root, Node n1, Node n2) {
        if (root == null || root.data == n1.data || root.data == n2.data ||
                (n1.data < root.data && root.data < n2.data) || (n2.data < root.data && root.data < n1.data))
            return root;
        if (root.data < n1.data && root.data < n2.data)
            return LCA(root.right, n1, n2);
        return LCA(root.left, n1, n2);
    }
}

Was this solution helpful?