Sunday, November 2, 2014

Lowest Common Ancestor (LCA) in a Binary Tree

Reference :-

My approach :-
Method using single traversal & flags(v1 and v2) given in article can be improved further.
There we call find(lca, n2) & find(lca, n1). 
So you are traversing tree twice for looking up two keys.
What if n1 is somewhere down n2 ? All the traversal to reach till n1 is done again. 
Instead you should traverse tree just once and keep track of values found. If you find one key still continue searching further for other key. So all the traversal till this point is not needed again. 
Once you find both keys stop search.

So you maintain two flags to indicate of values are found. Initially both flags are false.
If root is equal to one value then corresponding flag is set.
Then we search sub-trees to in same way. 
After traversal is complete; if if both flag were false before this node checking and both flag are true after this node checking then this node it LCA

Java implementation 
Code is also shared at

package tree;

public class TreeNode {
int numKey;
char charKey;
public TreeNode left, right;

TreeNode(int keyVal){

TreeNode(char keyVal){

TreeNode(char keyVal,TreeNode leftChild, TreeNode rightChild){

public static TreeNode findLCA(TreeNode root, int val1, int val2){
LCA lcaObj = new LCA();
return findLCA_internal(root,lcaObj);


private static TreeNode findLCA_internal(TreeNode root,LCA lcaObj ){
if(root==null) return null;

if(lcaObj.val1Found && lcaObj.val2Found){
// both values are found at previous level so do nothing more
return null;
boolean val1FlagBefore = lcaObj.val1Found;
boolean val2FlagBefore = lcaObj.val2Found;

if(!lcaObj.val1Found && root.numKey==lcaObj.val1){
}if(!lcaObj.val2Found && root.numKey==lcaObj.val2){
TreeNode lcaPresentInLeftTree = findLCA_internal(root.left,lcaObj);
if(lcaPresentInLeftTree !=null){
return lcaPresentInLeftTree;
TreeNode lcaPresentInRightTree  = findLCA_internal(root.right,lcaObj);
if(lcaPresentInRightTree!=null) {
return lcaPresentInRightTree;
// LCA is not presnt in left tree nor it is present in right tree. So check if this node itself if LCA
//  before this node was checked ;val1 flag was false and afterwards it is true.
// before this node was checked; val2 flag was false and and afterwards it is true.
// This root is the LCA
if(!val1FlagBefore && lcaObj.val1Found && !val2FlagBefore && lcaObj.val2Found){
return root;
// So either or both of keys are not present in this tree
return null;



public static void main(String[] args) {
/ \
   20  30
   / \
  40 50
TreeNode root = new TreeNode(10);
root.left= new TreeNode(20);
root.left.left= new TreeNode(40);
root.left.right= new TreeNode(50);
root.right= new TreeNode(30);

TreeNode lcaNode = null;
lcaNode = findLCA(root, 50, 40);
System.out.println("findLCA(root, 50, 40)" + lcaNode.numKey );
lcaNode = findLCA(root, 30, 40);
System.out.println("findLCA(root, 30, 40)"+ lcaNode.numKey );
lcaNode = findLCA(root, 30, 20);
System.out.println("findLCA(root, 30, 20)"+ lcaNode.numKey );
lcaNode = findLCA(root, 50, 20);
System.out.println("findLCA(root, 50, 20)"+ lcaNode.numKey );



class LCA{
int val1,val2;
boolean val1Found=false;
boolean val2Found=false;


findLCA(root, 50, 40)20
findLCA(root, 30, 40)10
findLCA(root, 30, 20)10
findLCA(root, 50, 20)20

No comments:

Post a Comment