0

System.out.println(ancestor.data) inside LCA() method is throwing NPE even though my recursion findlca() is setting ancestor value to a node with value 4. I can see this from using debug pointers. Once I come outside my recursion ancestor field is set to null. Object reference shouldn't change, right?

public class LCA {
    
    static class Node {
        int data;
        Node left;
        Node right;
        Node(int data){
            this.data =data;
        }
    }
    
    public static Node lca(Node root, int v1, int v2) {
        Node ancestor = null;
        findlca(root, v1, v2, ancestor);
        System.out.println(ancestor.data);
        return ancestor;
    }
    
    public static boolean findlca(Node node, int v1, int v2, Node ancestor){
        if(node==null){
            return false;
        }
        boolean nodeMatch = false;
        if(node.data==v1 || node.data==v2){
            nodeMatch = true;
        }
        boolean leftMatch = findlca(node.left, v1, v2, ancestor);
        boolean rightMatch = findlca(node.right, v1, v2, ancestor);
        if((leftMatch && rightMatch) || (leftMatch && nodeMatch) || (rightMatch && nodeMatch)){
            ancestor = node;
        }
        return leftMatch || nodeMatch || rightMatch;
    }
    
    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(7);
        
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        
        root.right.left = new Node(6);
        Node ancestor = lca(root, 1, 7);
        System.out.println(ancestor.data);
    }
}
Teja duggirala
  • 63
  • 6

2 Answers2

1

I think article like this will answered on your question.

Whenever an object is passed as an argument, an exact copy of the reference variable is created which points to the same location of the object in heap memory as the original reference variable.
As a result of this, whenever we make any change in the same object in the method, that change is reflected in the original object. However, if we allocate a new object to the passed reference variable, then it won't be reflected in the original object.

To fix your code you can add empty constructor in class Node, create object with empty constructor and fill his fields in findlca(...)

bylbyl9tor
  • 31
  • 1
  • 1
  • 5
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Apr 13 '22 at 22:40
1

Java is pass-by-value, not pass-by-reference, so ancestor variable in findlca() is not the ancestor you declared at the start of lca(), but a copy of it. Sure, they may refer to the same object, but they themselves are different variables.

To fix it, simply assign ancestor in lca() to the output of findlca().

ancestor = findlca(root, v1, v2, ancestor)
bui
  • 1,576
  • 1
  • 7
  • 10