Find Lowest Command Ancestor fail on tree search (Not algorithm issue, but more a Java issue)

Question

Very simple tree problem, somehow the result is null (which should be 1, since 1 is 2 & 3's parent node), cannot find the cause. The method itself already pass the Leetcode online judge.

Here is the link to the problem:

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

public class LowestCommonAncestor2 {

    public static TreeNode mockTree() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.left = node2;
        node1.right = node3;
        return node1;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode t1, TreeNode t2) {
           if (root == null || root == t1 || root == t2) {
               return root;
           }

           TreeNode left = lowestCommonAncestor(root.left, t1, t2);
           TreeNode right = lowestCommonAncestor(root.right, t1, t2);

           if (left != null && right != null) 
               return root;
           if (left != null) 
               return left;
           if (right != null) 
               return right;
           return null;
    }

    public static void main (String [] args) {
        LowestCommonAncestor2 test = new LowestCommonAncestor2();
        TreeNode root = mockTree();
        TreeNode target1 = new TreeNode(2);
        TreeNode target2 = new TreeNode(3);
        TreeNode result = test.lowestCommonAncestor(root, target1, target2);
        System.out.println(result);
    } 
}

and the TreeNode are defined as following:

public class TreeNode {
     public int val;
     public TreeNode left, right;
     public TreeNode(int val) {
         this.val = val;
         this.left = this.right = null;
     }
}

is it required that a TreeNode doesn't have a pointer to Parent ? — niceman
This is the TreeNode provide by the Leetcode, so I dont think pointer is a option. — Patrick

Chris Gong Chris Gong · Accepted Answer · 2016-07-04T23:40:43

The error is happening because of this line of code

if (root == null || root == t1 || root == t2)

Think about exactly what you are comparing when executing this method

TreeNode result = test.lowestCommonAncestor(root, target1, target2);

When you call the LCA method, none of the conditions in the first if statement will evaluate to true because none of the statements are true, which is correct. However, now let's get to the first recursive calls,

TreeNode left = lowestCommonAncestor(root.left, t1, t2);
TreeNode right = lowestCommonAncestor(root.right, t1, t2);

For lowestCommonAncestor(root.left, t1, t2), carefully think about the first if statement. root in this case is now node2, while t1 and t2 are still the nodes target1 and target2 defined in the main like before. But wait, this is why the problem is occurring. You would expect the statement root == t1 to evaluate to true, but it's not evaluating to true and here's why. node2 and target1 are two different objects, and Java's == operator doesn't do what you think it does here. When comparing objects using the == operator, the addresses of the objects are being compared rather than the actual contents of the objects. Therefore, since node2 and target1 occupy different spaces of data in your program, they do not have the same addresses. You will see the == operator more commonly used for comparing primitive types in Java such as int and char because it's not the same as comparing objects. This is why you see the .equals method used to compare Strings in Java, because Strings are objects.

So what's the solution?

Make an equals method in your TreeNode class that returns a boolean and takes another TreeNode object as a parameter. Also, make sure that this method is an instance method rather than a static method so that the execution of this method in code looks like this,

public boolean equals(TreeNode node){ //method address
    //rest of the method has to be implemented yourself
    //ask yourself, how are two treenodes considered equal in your situation?
}

And lastly, replace root == t1 with

root.equals(t1)

and root == t2 with

root.equals(t2)

Find Lowest Command Ancestor fail on tree search (Not algorithm issue, but more a Java issue)

2 Answers

Explanation