Monday, February 9, 2015

Find lowest common ancestor in a binary tree

This is very common problem. Given a binary tree (not a binary search tree) and two values say n1 and n2, write a program to find the least common ancestor. And our assumption is that the keys in the tree are unique. 


Binary tree has a very nice property is that it is a data structure naturally fit for recursive and divide/conquer. 
We can always express most of tree algorithm in the following form:
That is we do some computing on the left and right subtrees such as search and return the parent, then the parent node will further process the results, do some computation, and return the result. 
In the following algorithm we do DFS search on the binary tree, return true or false if the node is found, then we have two cases when we meet the LCA:



Fn(parent) = Operation(Fn(left_child) + Fn(right_child))
1. the node's left and right tree have the target values
2. the current node has one of the target values, and one of its subtrees has the one of the target values.


public Node findLCAInBinaryTree(Node root, int v1, int v2){
    Node[] found = new Node[1];
    findLCAInBinaryTree(root, v1, v2, found);
    return found[0];
}

public boolean findLCAInBinaryTree(Node curr, int v1, int v2, Node found){
    if(curr==null)
        return false;
   
    boolean left = findLCAInBinaryTree(curr.left, v1, v2, found);
    boolean right = findLCAInBinaryTree(curr.right, v1, v2, found);
    // case 1
    if(left && right)
          found[0] = curr;
    //case 2
    if((curr.value == v1 || curr.value == v2) && (left || right))
          found[0] = curr;  
     
     return left || right || curr.value == v1|| curr.value==v2;      
}

No comments:

Post a Comment