Sunday, August 17, 2008

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]

7 comments:

  1. Using a parent pointer makes things easy, but typically parent pointer is not kept in the node.

    ReplyDelete
  2. The solution for the same with ILLUSTRATIVE PICTURES and complete working code in Java at,

    http://technicalypto.blogspot.com/2010/02/find-common-parent-in-binary-search.html

    ReplyDelete
  3. 50
    / \
    25 75
    /
    65
    /
    55
    Will this algorithm work for LCA of 55 and 65?

    ReplyDelete
  4. what if the parent link is not there??

    ReplyDelete
  5. LCA of a Binary Search Tree is easier as shown here,
    http://www.ritambhara.in/lowest-common-ancestor-in-binary-search-tree/

    ReplyDelete
  6. @kamal, the code you point out uses recursion instead of looping. compared to looping, recursion code is readable but also typically slower.

    ReplyDelete