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);
}
/*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);
}
