Find the Lowest Common Ancestor of Two Tree Nodes

Given a binary tree and two tree nodes, write a method to find LCA (Lowest Common Ancestor) of the two nodes.

Example:  
       1              
      / \            
     2   3   
    / \ / \       
   4  5 6  7    
    ==> LCA of 6 and 4 is 1,    
    LCA of 4 and 5 is 2.

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

The lowest common ancestor node N of two nodes n1 and n2 is defined as the lowest node in the tree T that has both n1 and n2 as descendants and the paths from N->n1 and N->n2 are the shortest possible.

Final hint! You should be able to code the problem on viewing this.

1. Declare two variables to keep track of the left and right accessors at each level. Let's call them tempLeft and tempRight.

2. As part of the base condition, if root is null, return root.

3. If root is equal to node a or node b, return root.

4. Make a recursive call with the left node of the root as the input and assign it to leftTemp. Similarly, assign the output of the recursive call with the right node to tempRight.

5. If either leftTemp or rightTemp are null, return null. Else, return the node that is not null.

public TreeNode findLCA(TreeNode root, TreeNode a, TreeNode b) {
                       


}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Find the Lowest Common Ancestor of Two Tree Nodes

Quick hint to get things rolling

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :