inserting nodes into a binary tree in java question

Question

im coming from c++ to java and i am confused on binary trees with java. is the only way to have a Node class is to make it an inner static class? all the examples i see do this. However, the way im doing it is i have a node class and a binarytree class uses this node class. but i keep getting an error when i try inserting into the tree after the second insert. i get an exception at this line if(dataIn <= nodeIn.getLeft().getData()){

I am confused as to what i did wrong.... here is my code for insert that i have. thanks in advance..

public void insert(int dataIn){
    root = insert(root, dataIn);
}

private Node insert(Node nodeIn, int dataIn){
    if(nodeIn==null){
        nodeIn = new Node(null, null, dataIn);
    }else{
        if(dataIn <= nodeIn.getLeft().getData()){
            nodeIn.setLeft(insert(nodeIn.getLeft(), dataIn));
        }else{
            nodeIn.setRight(insert(nodeIn.getRight(), dataIn));
        }
    }

    return nodeIn;
}

Answer 1

Part of the reason it's confusing is that "Node" should not be a parameter to the insert method, you should be calling an insert method defined in node.

So let's say you hold the "Root" node in your "normal code"--let's call it "rootNode" just to be obscure.

Okay, so your code to insert into the tree would be:

rootNode.insert(newValue);

Easy enough.

Now to define that method.

public class Node {
    private int value;
    private Node lower;
    private Node higher;

    public void insert(int newValue) {
        if (newValue < value)
            if(lower == null)
                lower=new Node(value);
            else
                lower.insert(newValue);
        else
            if(higher == null)
                higher=new Node(value);
            else
                higher.insert(newValue);
      }

 // and you'll need a constructor
    public Node(int value) {
        this.value=value;
    }
}

This should read much more clearly. I'm going to hit "Post" then I'm going to edit it and figure out how to easily refractor that evil evil copy & paste code.

On second thought, I'll leave it there because it's more readable. The best fix I can see is to make the nodes an array, then you get:

public class Node {

    private int value;
    private Node[] nodes=new Node[2];
    private final int LOWER=0;
    private final int HIGHER=1;

    public void insert(int newValue) {
        int index=LOWER;
        if (newValue > value)
            index=HIGHER;

        if(nodes[index] == null)
            nodes[index]=new Node(value);
            else
                nodes[index].insert(newValue);
        }
    }

But I won't replace the original because, as I said, it's clearer.

I recommend the refactoring book for more of this. It really does help simplify your code once you really get OO. Passing an object to an otherwise static method (one that doesn't use member variables) is a dead give-away.

With more considerations about @ted's comment and OO--getLeft and getRight shouldn't even be an issue. Neither is necessary outside the abstraction.

In general what you probably need is these methods in Node:

public boolean doesContain(int value) {
     if(value == this.value)
         return true
     else
         return nodes[ this.value < value ? LOWER : HIGHER].doesContain(value);
}

and maybe

public void getValuesSorted(LinkedList l) {
    nodes[LOWER].getValuesSorted(l);
    l.put(value);
    nodes[HIGHER].getValuesSorted(l);
}

Then you don't even need to expose that it's a tree you are dealing with--beter OO abstraction.