Why my recursion doesnt work? (Java)

Question

I want to find the Lowest Commone Ancestor of a binary tree (not a binary search tree!) To this end I use the second method from this web page: http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/ Basically, in Java my method looks like this:

  private static int LCA2(Node root, Node n1, Node n2)
  {
    if(root == null) return -1;

    if(root.id == n1.id || root.id == n2.id) return root.id;

    int left = LCA2(root.left, n1, n2);
    int right = LCA2(root.right, n1, n2);

    if(left != -1 && right != -1) return root.id;

    if(left != -1) return LCA2(root.left, n1, n2);

    return LCA2(root.right, n1, n2);
}

And this is the main() function:

   public static void main (String[] args)
   {
        List<Node> tree = new ArrayList<Node>();

        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n7 = new Node(7);
        Node n8 = new Node(8);
        Node n9 = new Node(9);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n5.left = n6;
        n3.left = n8;
        n3.right = n7;
        n8.right = n9;

        res = new ArrayList<Integer>();
        int k = 2;

//      findKNodes(n1, k);
//      for (int i = 0; i < res.size(); i++)
//          System.out.print(res.get(i) + " ");

        int res = LCA2(n1, n4, n6);

        System.out.println(res);

    }

Basically my tree looks like this:

    1
   / \
  2   3
 / \  /\
4  5  8 7
  /   \
 6     9

And I run my recursive function LCA(Node root, node n1, node n2) with root = 1, n1 = 4, n2 = 6; So after the first recursive call of LCA I expect the finction to return left = 4, right = -1 and to recurse on the left subtree of the root. However it returns left = 6, right = -1, which is not a problem for the very first iteration, but for the next it goes to infinity cycle and I dont know how to fix this.

EDIT: the code for class Node:

public static class Node
{
    int id;
    Node left;
    Node right;

    public Node (int id)
    {
        this.id = id;
    }
}

Answer 1

You already got a answer by @Khaled and @Pham Trung but let me help you to clear the recursive call trace.

    1. LCA2(1, 4, 6) -> left = LCA2(2, 4, 6) = 2 (by 2 step because left = 4 != -1 and right = 6 != -1 means root.id is LCA which is 2)
                        right = LCA2(3, 4, 6) = -1 

    2. LCA2(2, 4, 6) -> left = LCA2(4, 4, 6) = 4 (by 2a step)
                        right = LCA2(5, 4, 6) = 6 (by 2b step)

    2a. LCA2(4, 4, 6) -> return root.id which is 4
    2b. LCA2(5, 4, 6) -> left = LCA2(6, 4, 6) = 6(by 2ba step)
                         right = LCA2(null, 4, 6) = -1  

    2ba. LCA2(6, 4, 6) -> return root.id which is 6

As a final call 2 != -1 so it returns 2 as a answer.
Please revert if you need more clarification. You can find java code for tree problems of geeksforgeeks in following URL if you are stuck. https://github.com/harmishlakhani/AlgoAndDataStructure/blob/master/AlgoAndDataStructure/src/com/ds/tree/BinaryTreeUtility.java

Answer 2

Note: After fixing issue about recompiling the code (which I has mentioned in my comment), here is the tip to help your code run faster.

To avoid calling the same method LCA2 twice, you should rewrite your method as follow:

private static int LCA2(Node root, Node n1, Node n2)
{
    if(root == null)
        return -1;

    if(root.id == n1.id || root.id == n2.id)
        return root.id;

    int left = LCA2(root.left, n1, n2);
    int right = LCA2(root.right, n1, n2);

    if(left != -1 && right != -1)
        return root.id;

    if(left != -1)
        return left; // you don't need to call the same routine again here, which will cost you some time.

    return right; //Similar reason

}