Lowest Common Ancestor (LCA) in Binary Trees

LCA is a binary search tree (BST) is simple. For any nodes x and y, the LCA is the first node which lies between x and y starting from root.

Node getLCA_BST(Node root, Node x, Node y):
    Node curr = root
    while !(x < curr && curr < y): // x.value < curr.value
        if curr < x && curr < y:
            curr = curr.right
        else: //x < curr && y < curr
            curr = curr.left
    return curr // assume x and y are in the tree

[Hat tip to PIE]


In binary tree (BT), we have to:
- use a parent node pointer to get their paths in O(h) or O(logn) time
- find the intersecting node within the paths starting from root

Use a stack to save the paths for nodes x, y.

class TreeNode:
    int value
    TreeNode left
    TreeNode right
    TreeNode parent

TreeNode getLCA_BT(TreeNode root, TreeNode x, TreeNode y):
    Stack sx = getPath(x)
    Stack sy = getPath(y)
    return getLCAFromPaths(sx, sy)

Stack getPath(Node n):
    Stack sn = new Stack()
    while (n != null):
        sn.push(n)
        n = n.parent
    return sn

TreeNode getLCAFromPaths(Stack sx, Stack sy):
    if sx == null || sy == null
        || sx.empty() || sy.empty():
        throw
    lca = null
    while !sx.empty() && !sy.empty()
        && sx.peek() == sy.peek():
        lca = sx.pop()
        sy.pop() //ignore
    return lca

[Hat tip to B.]


Without parent node: 

If both nodes are present in current node's left subtree then recurse with left node. Same for right subtree and right node. The node where x, y are not in node's subtrees is the lca.

node lca-bt-check(node, x, y):
    if node == null:
        throw
    if x == null || y == null:
        throw
    lca = lca-bt(node, x, y)
    if lca == node && (!is-present(node, x) || !is-present(node, y)):
        throw
    return lca

// inefficient
node lca-bt(node, x, y):
    if node == null:
        return null
    if is-present(node.left, x) && is-present(node.left, y):
        return lca(node.left, x, y)
    if is-present(node.right, x) && is-present(node.right, y):
        return lca(node.right, x, y
    return node

bool is-present(node, x):
    if node == null:
        return false
    if node == x:
        return true
    return is-present(node.left, x) || is-present(node.right, x)

Efficient way is to use the "bubble up" during dfs backtracking. Once x is found, bubble it up. Same for y. The very first node with a node's left and right as x and y (left and right are not null) is the lca. Once lca is found, bubble it up.

// efficient
node lca-bt(node, x, y):
    if node == null:
        return null
    
    // node is x or y
    if node == x || node == y:
        return node
    
    // bubble up lca
    left = lca-bt(node.left, x, y)
    if left != null && left != x && left != y:
        return left
    right = lca-bt(node.right, x, y)
    if right != null && right != x && right != y:
        return right
    
    // lca
    if left != null && right != null: // i.e. left, right are x, y
        return node
    
    // bubble up x or y
    if left != null:
        return left
    if right != null:
        return right
    
    // x, y not in node's subtree
    return null

Corner cases:
- When x or y is not present in tree, then throw (or lca is null).
- When x is ancestor of y, then lca is x.
- When x == y, then lca is x or y.

lca-bt-check(node, x, y):
    if node == null:
        throw
    if x == null || y == null:
        throw
    if x == y:
        if !is-present(node, x):
            throw
        return x // or y
    lca = lca-bt(node, x, y)
    if lca == null:
        throw
    // corner case when lca is x or y
    if lca == x && !is-present(lca, y) || lca == y && !is-present(lca, x):
        throw
    return lca

{Hat tip to ctci]