Thread: Binary Search Tree inorder tree traversal

Hi I'm very new to Java and I'm trying to write some code to create a Binary Search Tree with the goal of outputting a list of integers using the inorder tree traversal method.
I've got as far as this:

public class BinarySearchTree {
 
 public class Node {
        private int value;
        private Node right;
        private Node left;
        //construct node
        //set current left and right vertices of root to null
        public Node(int value){
            this.value = value;
            left = null;
            right = null;
 
        }
        public Node leftNode() {
       return left;
   }
        public Node rightNode() {
       return right;
   }
        public int getNodeValue(){
            return value;
        }
 
    private Node root;
    //construct binary search tree
    public void BinarySearchTree() {
        root = null;
            }
    //Establish that if the tree is empty, then the value of the root is null
    public boolean ifEmpty()
    { 
        if (root == null) {
            return true;
    }
        else { return false;
                }
    }
    //Develop ability to add values into the binary search tree
    public boolean insert(int value)
    { if (root == null) {
        root = new Node(value);
        return true;
    }
    else { if  (value == this.value)
            { return false; }
            else if (value <this.value) {
                  if (left == null) {
                        left = new Node(value);
                        return true;
                  } else {
                    return left.insert(value);
                }
            } else if (value > this.value) {
                  if (right == null) {
                        right = new Node(value);
                        return true;
                  } else {
                    return right.insert(value);
                }
            }
            return false;
 
       }
    }
 
    public void sortedList(){
        sortedList(root);
        }      
    private void sortedList(Node root){
        if (root == null) 
            return;
        sortedList( root.leftNode() );
        System.out.println(root.value + " ");
        sortedList ( root.rightNode() );
 
 
 
    }
 }
 
    public static void main(final String[] args){
 
 
    }
}

I've been following a tutorial and have been looking at some code on the internet, I'm not quite sure how I'm supposed to know if the sortedList method is sufficient to output, in order, a list of integers that has been put into the tree. Specifically the sortedList method I wrote with help of someone elses BST code and so I don't if it is written correctly in relation to the tree I have and the fields/objects that I have defined.
Also how would I go about entering some numbers into the code to see the tree in action? Sorry If I'm coming across as quite dense but I've only been working with Java for the past couple of weeks.

Originally Posted by Norm

Create an instance of the class in the main() method and call some of its methods.

I have tried writing this:

  public static void main(final String[] args){
      int[] anArray = { 7, 3, 1, 6, 9, 0, 4, 5, 2, 8};
      value = anArray[0];
      Node firstnode = new Node(value);
      firstnode.insert(value);
    }

However I get a "non-static variable cannot be referenced from a static context" for lines 2-4, is there any obvious reason why this is occurring?

It looks like the definitions of the Node class and the BST class are mixed together.

So should my Node class be in a separate file that the Binary Search File then calls methods from? Is this a cosmetic issue or will it end in complications in the final code?

Thanks for the help, it's much appreciated!

BinarySearchTree.java:96: error: non-static variable value cannot be referenced
from a static context
value = anArray[0];
^
BinarySearchTree.java:97: error: non-static variable value cannot be referenced
from a static context
Node firstnode = new Node(value);
^
BinarySearchTree.java:98: error: non-static variable value cannot be referenced
from a static context
firstnode.insert(value);

That's what I get from the cmd window.

Okay right, I understand that more clearly now. I also see the problem with the node class interfering with insert. However when I define the Node class as an inner class it looks like the fields defined in the Node class (root, left, right etc.) no longer know where to point to when they're used in the insert method?

Okay I understand what you're saying, I currently have this code:

public class BinarySearchTree {
 
 
  public static class Node {
        private int value;
        private Node right;
        private Node left;
        //construct node
        //set current left and right vertices of root to null
        public Node(int value){
            this.value = value;
            left = null;
            right = null;
 
        }
        public Node leftNode() {
       return left;
   }
        public Node rightNode() {
       return right;
   }
        public int getNodeValue(){
            return value;
        }
 
    private Node root;
  }
      //construct binary search tree
    public void BinarySearchTree() {
        root = null;
            }
    //Establish that if the tree is empty, then the value of the root is null
    public boolean ifEmpty()
    { 
        if (root == null) {
            return true;
    }
        else { return false;
                }
    }
    //Develop ability to add values into the binary search tree
    public boolean insert(int value)
    { if (root == null) {
        root = new Node(value);
        return true;
    }
    else { if  (value == this.value)
            { return false; }
            else if (value <this.value) {
                  if (left == null) {
                        left = new Node(value);
                        return true;
                  } else {
                    return left.insert(value);
                }
            } else if (value > this.value) {
                  if (right == null) {
                        right = new Node(value);
                        return true;
                  } else {
                    return right.insert(value);
                }
            }
            return false;
 
       }
    }
 
    public void sortedList(){
        sortedList(root);
        }      
    private void sortedList(Node root){
        if (root == null) 
            return;
        sortedList( root.leftNode() );
        System.out.println(root.value + " ");
        sortedList ( root.rightNode() );
 
    }
 
 
 
 
  public static void main(final String[] args, int value){
      int[] anArray = { 7, 3, 1, 6, 9, 0, 4, 5, 2, 8};
      value = anArray[0];
      BinarySearchTree bst = new BinarySearchTree();
      boolean aVal = bst.insert(value);
 
    }
}

When I implement it I get the following 14 errors:

BinarySearchTree.java:41: error: cannot find symbol
root = null;
^
symbol: variable root
location: class BinarySearchTree
BinarySearchTree.java:46: error: cannot find symbol
if (root == null) {
^
symbol: variable root
location: class BinarySearchTree
BinarySearchTree.java:54: error: cannot find symbol
{ if (root == null) {
^
symbol: variable root
location: class BinarySearchTree
BinarySearchTree.java:55: error: cannot find symbol
root = new Node(value);
^
symbol: variable root
location: class BinarySearchTree
BinarySearchTree.java:58: error: cannot find symbol
else { if (value == this.value)
^
symbol: variable value
BinarySearchTree.java:60: error: cannot find symbol
else if (value <this.value) {
^
symbol: variable value
BinarySearchTree.java:61: error: cannot find symbol
if (left == null) {
^
symbol: variable left
location: class BinarySearchTree
BinarySearchTree.java:62: error: cannot find symbol
left = new Node(value);
^
symbol: variable left
location: class BinarySearchTree
BinarySearchTree.java:65: error: cannot find symbol
return left.insert(value);
^
symbol: variable left
location: class BinarySearchTree
BinarySearchTree.java:67: error: cannot find symbol
} else if (value > this.value) {
^
symbol: variable value
BinarySearchTree.java:68: error: cannot find symbol
if (right == null) {
^
symbol: variable right
location: class BinarySearchTree
BinarySearchTree.java:69: error: cannot find symbol
right = new Node(value);
^
symbol: variable right
location: class BinarySearchTree
BinarySearchTree.java:72: error: cannot find symbol
return right.insert(value);
^
symbol: variable right
location: class BinarySearchTree
BinarySearchTree.java:81: error: cannot find symbol
sortedList(root);
^
symbol: variable root
location: class BinarySearchTree
14 errors

At the risk of you wasting too much of your own time, and also so I can learn Java better myself, are there any hints you could give as to how I could implement the logic required in the BST class so that the fields recognise that they originate from the Node class?

Thanks

I'm not sure how I can solve the problem I now have, I've tried replacing the left and right in the insert method with Node.left/Node.right but I now get an error saying that they can't be referenced from a static context.

I've changed my code quite substantially, and now I have seem to have got a working bit of code, however now when I run it in the command window I get the following error which I can't seem to make sense of:

Exception in thread "main" java.lang.NoClassDefFoundError: BinarySearchTree (wro
ng name: binary/search/tree/BinarySearchTree)
at java.lang.ClassLoader.defineClass1(Native Method)
at java.lang.ClassLoader.defineClass(ClassLoader.java :791)
at java.security.SecureClassLoader.defineClass(Secure ClassLoader.java:14
2)
at java.net.URLClassLoader.defineClass(URLClassLoader .java:449)
at java.net.URLClassLoader.access$100(URLClassLoader. java:71)
at java.net.URLClassLoader$1.run(URLClassLoader.java: 361)
at java.net.URLClassLoader$1.run(URLClassLoader.java: 355)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(URLClassLoader.j ava:354)
at java.lang.ClassLoader.loadClass(ClassLoader.java:4 23)
at sun.misc.Launcher$AppClassLoader.loadClass(Launche r.java:308)
at java.lang.ClassLoader.loadClass(ClassLoader.java:3 56)
at sun.launcher.LauncherHelper.checkAndLoadMain(Launc herHelper.java:482)

My code now looks like:

public class BinarySearchTree {
 
    //set up node with fields 
    //determining the node's 
    //placement in the tree 
    //relative to the nodes around it
 
  public class Node {
       public Node parent;
       public Node left;
       public Node right;
 
       private int value;
 
       public Node(int value){
           this.parent = null;
           this.left = null;
           this.right = null;
           this.value = value;                  
       }
 
       public int getValue(){
          return this.value;
      }
       public void setValue(int value){
           this.value = value;
       }
 
  }
 
  private Node root;
 
  //Construct the Binary Search Tree with current root = null
 
  public BinarySearchTree(){
      this.root = null;
  }
  public Node returnRoot(){
      return root;
  }
  public void insertNode(int id)
  {
      Node newNode = new Node(id);
      newNode.value = id;
      if (root == null){
          root = newNode;
      }
      else {
          Node current = root;
          Node parent;
          while(true)
          {
              parent = current;
              if(id < current.value)
              {
                  current = current.left;
                  if(current==null){
                      parent.left = newNode;
                      return;
                      }
                    }
              else {
                  if(current==null){
                      parent.right = newNode;
                      return;
                  }
              }
          }
 
      }
  }
 
  public void sortedList(Node node){
        if (root != null) {
        sortedList( node.left );
        System.out.println(node.value + " ");
        sortedList( node.right );
           }
}                  
 
  public static void main(final String[] args) 
  {
      int value;
      BinarySearchTree tree1 = new BinarySearchTree();
      tree1.insertNode(7);
      tree1.insertNode(1);
      tree1.insertNode(0);
      tree1.insertNode(9);
      tree1.insertNode(3);
      tree1.insertNode(6);
      tree1.insertNode(2);
      tree1.insertNode(4);
      tree1.insertNode(5);
      tree1.insertNode(8);
 
      System.out.println("Sorted list of integers from tree: ");
              tree1.sortedList(tree1.returnRoot());
 
    }
}

and when I have it written in Netbeans it doesn't flag up any errors.

Thanks for the help.

When I try to run it in Netbeans, it just seems to run forever, I left it going for over 20 mins and it didn't complete the running process?

I've narrowed it down to the while section in my code I've tried implementing a count system so that it acts while the count is below a certain number.

public static int count = 1;
.
.
.
while(count < 10)
          {
              parent = current;
              if(id < current.value)
              {
                  current = current.left;
                  if(current==null){
                      parent.left = newNode;
                      count++;
                      return;
                      }
                    }
              else {
                  if(current==null){
                      parent.right = newNode;
                      count++;
                      return;
                  }
              }
          }

I'm entering 10 numbers into the tree so I assumed if I started the count at 1 and said for count < 10 it would have to stop. However it still seems to be an infinite loop and no matter how low I make the while expression it doesn't stop running. If I take away the while statement it runs the iteration once and stops.

--- Update ---

Update: for count < 3 it works but only produces the first three integers from my main method. For any more it seems to become infinite

--- Update ---

Update: I've finally managed to get it to work but for some reason I need to set the count to be less than an arbitrarily high number. Right now 100 suffices, but is there any way I could set the count to be less than a number that would work for any number of integers added?