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:
- search (DFS/BFS) the two nodes x and y to get their paths in O(n) time OR 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

class Node:
    int value 
    Node left 
    Node right
    Node parent

class ListNode:
    Node value //Node is Binary Tree node
    ListNode next

Node getLCA_BT(Node root, Node x, Node y):
    ListNode lx = getPath(x)
    ListNode ly = getPath(y)
    return getLCAFromPaths(lx, ly)
    
ListNode getPath(Node n):
    ListNode ln = null 
    ListNode after = null
    while (n != null):
        ln = new ListNode()
        ln.value = n
        ln.next = after
        after = ln
        n = n.parent
    return ln

Node getLCAFromPaths(ListNode lx, ListNode ly):
    Node lca = null
    while (lx.value == ly.value): // lx.value.value
        lca = lx.value //or ly.value
        lx = lx.next
        ly = ly.next
    return lca

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

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