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):
    Node lca, x, y = null
    do:
        lca = x //or y
        x = sx.pop()
        y = sy.pop()
    while (x == y)
    return lca

[Hat tip to B.]


Without parent node: 

Check to see if both nodes are present in current node's subtree and return null if not. Check left and right subtrees. If both nodes are not present in either left or right subtrees, then current node is lca. Bubble up lca.
lca-bt-check(node, x, y):
    if node == null:
        throw
    if x == null || y == null:
        throw
    if !is-present(node, x) || !is-present(node, y):
        throw
    return lca-bt(node, x, y)

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

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 tactic. 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
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

{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