Java Tree finding the Lowest Common Ancestor (LCA)

This extends Java Preorder Tree Traversal : recursive and iterative flattening of tree. This is also a very popular coding interview question.

Q. Find out the LCA (i.e. Lowest Common Ancestor) for nodes a and b where a = 3 and b = 4 as shown below?

A. The Node a has ancestors : 2 and 1.  The Node b has ancestors 2 and 1. The Lowest Common Ancestor is Node with value 2. Let's look at the code for this.


Step 1: Define the TreeNode class as did before but define the "parent" attribute so that each node knows not only who the children are, but also who the parent is as well.

 
package com.mycompany.app14;

public class TreeNode
{
    
    private int value;
    //children
    private TreeNode left;
    private TreeNode right;
    //parent
    private TreeNode parent;
    
    public TreeNode(int value, TreeNode left, TreeNode right)
    {
        super();
        this.value = value;
        this.left = left;
        this.right = right;
    }
    
    public int getValue()
    {
        return value;
    }
    
    public void setValue(int value)
    {
        this.value = value;
    }
    
    public TreeNode getLeft()
    {
        return left;
    }
    
    public void setLeft(TreeNode left)
    {
        this.left = left;
    }
    
    public TreeNode getRight()
    {
        return right;
    }
    
    public void setRight(TreeNode right)
    {
        this.right = right;
    }
    
    public TreeNode getParent()
    {
        return parent;
    }
    
    public void setParent(TreeNode parent)
    {
        this.parent = parent;
    }
    
    @Override
    public String toString()
    {
        return "TreeNode [value=" + value + ", left=" + left + ", right=" + right + "]";
    }  
}

Step 2: The test class that constructs the tree structure and then calculates the LCA. Uses a Deque class, which is a LIFO structure.

 
package com.mycompany.app14;

import java.util.ArrayDeque;
import java.util.Deque;

public class TestFindCommonAncestor
{
    
    public static void main(String[] args)
    {
        TreeNode root = createOneTo6PreOrderTree();
        
        //Find the common ancestor for two given nodes a and b.
        
        //root node value is 1, node a is 3, and node b is 4
        //so, find the Least Common Ancestor for nodes representing values 3 and 4
        TreeNode commonNode = findLowestCommonAncestor(root.getLeft().getLeft(), root.getLeft().getRight());
        System.out.println(commonNode);
        
    }
    
    private static TreeNode createOneTo6PreOrderTree()
    {
        TreeNode leaf3 = new TreeNode(3, null, null);
        TreeNode leaf4 = new TreeNode(4, null, null);
        TreeNode leaf6 = new TreeNode(6, null, null);
        
        TreeNode node5 = new TreeNode(5, leaf6, null);
        TreeNode node2 = new TreeNode(2, leaf3, leaf4);
        
        TreeNode root1 = new TreeNode(1, node2, node5);
        
        //set parents
        leaf3.setParent(node2);
        leaf4.setParent(node2);
        
        leaf6.setParent(node5);
        
        node2.setParent(root1);
        node5.setParent(root1);
        
        return root1;
    }
    
    /**
     * @param a
     * @param b
     * @return
     */
    public static TreeNode findLowestCommonAncestor(TreeNode a, TreeNode b)
    {
        TreeNode oldNode = null;
        
        //find the parent nodes of a: should have 1, 2, and 3 for a = 3 
        Deque<TreeNode> parentNodesA = new ArrayDeque<TreeNode>();
        while (a != null)
        {
            parentNodesA.push(a);
            a = a.getParent();
        }
        
        //find the parent nodes of b: should have 1, 2 and 4 for b = 4
        Deque<TreeNode> parentNodesB = new ArrayDeque<TreeNode>();
        while (b != null)
        {
            parentNodesB.push(b);
            b = b.getParent();
        }
        
        //initially a and b will be null
        while (a == b && !parentNodesA.isEmpty() && !parentNodesB.isEmpty())
        {
            oldNode = a;
            a = parentNodesA.pop();
            b = parentNodesB.pop();
        }
        
        // a will be 3 and b will be 4 and oldNode will be 2
        if (a == b)
        {
            return a;                        // One node is descended from the other
        }
        else
        {
            return oldNode;                 // Neither is descended from the other
        }
        
    }
}

Step 3: Output

 
TreeNode [value=2, left=TreeNode [value=3, left=null, right=null], right=TreeNode [value=4, left=null, right=null]]