Root node always becoming NULL when traversing

Question

In this binary tree implementation I've tried to create an object from the BinaryTree class and thus insert elements and access them in order. While debugging it seems it's always returning root as NULL and thus the traversal fails.

I don't understand what I'm missing here. Where is my mistake?

public class BinaryTree{
    public static class Node{
        int value;
        Node left;
        Node right;
        public Node(int data){
            this.value = data;
            left = null;
            right = null;
        }
    }
    
    Node root;
    BinaryTree() { 
        root = null; 
    }
    
    public Node addrecursive(Node current,int value){
        if(current==null){
            return new Node(value);
        }else
        if(value<current.value){
            int n=current.value;
            current.left=addrecursive(current.left,value);
        }else
        if(value>current.value){
            int n=current.value;
            current.right=addrecursive(current.right,value);
        }else
        {
            return current;
        }
        return current;
    }

    public void add(int value) {
        Node n = null; 
        if(root==null) 
            root = addrecursive(root, value);
        else
            n = addrecursive(n, value);
    }

    private void createBinaryTree(){
        BinaryTree bt = new BinaryTree();
        bt.add(6);
        bt.add(4);
        bt.add(8);
        bt.add(3);
        bt.add(5);
        bt.add(7);
        bt.add(9);
        return;
    }

    private boolean containsNodeRecursive(Node current, int value) {
        if (current == null) {
            return false;
        } 
        if (value == current.value) {
            return true;
        } 
        return value < current.value
          ? containsNodeRecursive(current.left, value)
          : containsNodeRecursive(current.right, value);
    }

    public boolean containsNode(int value) {
        return containsNodeRecursive(this.root, value);
    }

    public void traverseInOrder(Node node) {
        if (node != null) {
            traverseInOrder(node.left);
            System.out.print(" " + node.value);
            traverseInOrder(node.right);
        }
    }
    void printInorder() {              //wrapper class for access without passing node
        traverseInOrder(root); 
    }

    public static void main(String [] args){
        BinaryTree bt =  new BinaryTree() ;     //object of class
        bt.createBinaryTree();              //creating the binary tree within that object 
        Boolean b = bt.containsNode(7); 
        System.out.println(b);
        System.out.println("\nInorder traversal of binary tree is " );
        bt.printInorder();
    }
}

Answer 1

There are several issues:

• In addrecursive the variable n is a local reference that is unrelated to your root. So whatever n = addrecursive(n, value); does with the null that you pass as argument, it doesn't do anything with the linked list that starts at root.

  It is actually quite simple... Your addrecursive function should only do:

      public void add(int value) {
          root = addrecursive(root, value);
      }
  

  The assignment to root is only really needed when root was null, but it doesn't hurt to always make that assignment. It is however important to pass root as argument, as that is the lead for where to append the new node.

• createBinaryTree creates a new local instance of BinaryTree (which is already strange, since this already is an instance), adds nodes to it, and then just discards that local instance -- all work done for nothing. There are different ways to solves this, but I would make this method a static method, and have it return the BinaryTree instance that it populated. The caller in main should then take that returned tree and assign it to its own variable:

      // Static!
      private static BinaryTree createBinaryTree(){
          BinaryTree bt = new BinaryTree();
          bt.add(6);
          bt.add(4);
          bt.add(8);
          bt.add(3);
          bt.add(5);
          bt.add(7);
          bt.add(9);
          return bt; // return the work that was done
      }
  
      public static void main(String [] args){
          // Call static function to get the reference to the new tree
          BinaryTree bt =  createBinaryTree(); 
          Boolean b = bt.containsNode(7); 
          System.out.println(b);
          System.out.println("\nInorder traversal of binary tree is " );
          bt.printInorder();
      }