Saturday, October 13, 2012

LCA - My attempt in deconstructing the recursive solution

Have given enough comments to explain the solution step by step.

/*LCA in a binary tree

Karumanchi Solution : Recursion (Found in http://www.flipkart.com/data-structures-algorithms-made-easy-java-1466304162/p/itmd34fz5jzb599u
Data Structures and Algorithms Made easy in Java
)

*/

//a, b -> parameters - nodes for which LCA is to be found out, they should remain unchanged throughout
BTNode LCA (BTNode root, BTNode a, BTNode b) {
BTNode left, right;

/*
Base Condition 1: if the root pointer is null - do nothing - return null
*/
if ( root == null ) return null;

/*
Base Condition 2: root pointer in this program is searching for a or b;
  so once we reach a or b, no more search is required.
*/
if ( root == a || root == b ) {
//Pointer comparison is enough here
return root;
}

/*
traverse left and right subtrees
*/

left  = LCA(root.getLeftChild(), a, b);
right = LCA(root.getRightChild(), a , b);

/*
Condition 1:

When nodes a and b are on either side (left and right) of a node,
we know that we have arrived at the LCA
*/
if ( !left && !right ) {
return root;
}

/*
Condition 2:

Condition that is required when both a and b are in the same subtree

        eg: 1
        2
        3

Here let a = 2 and b = 3; LCA of a and b in this case will be 1. 2 and 3 are in the same subtree

*/
return ( left ? left : right);

}

No comments:

Post a Comment