Binary Tree Operations

Question

I've been programming for about 5 years now, mostly in C++ and Java, while continuing my college education in Computer Science. As an adult student, I'm always looking for opinions and ways to improve from professionals in the field. Aside from reading from numerous text books, I've read these forums for tips and good programming practices to improve.

I'm posting a binary search tree in java to hear any and all feedback to continue with this trend of learning; any positive and negative criticism would be helpful to improve. Thanks in advance.

public class NewBinaryTree  {

    Node root; // top most node of tree

    public void addNode(int key, String name) { // adds node to tree
        Node newNode = new Node(key, name);

        if(root == null) {
            root = newNode;
        }
        else {
            Node focusNode = root;  
            Node parent;

            while(true) {
                parent = focusNode;

                if(key < focusNode.key){ // checks if the key is less than, then inserts left
                    focusNode = focusNode.leftChild;

                    if(focusNode == null) {
                        parent.leftChild = newNode;
                        return;
                    }
                }
                else { // key is greater than, so inserts on right
                    focusNode = focusNode.rightChild;

                    if(focusNode == null) {
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }

    public void inOrderTraverseTree(Node focusNode) { // in order tree traversal using recursion
        if(focusNode != null) { // checks if something is in there
            inOrderTraverseTree(focusNode.leftChild);
            System.out.println(focusNode);
            inOrderTraverseTree(focusNode.rightChild);
        }
    } // end in order tree traversal

    public void preOrderTraverseTree(Node focusNode) { // preorder tree traversal using recursion
        if(focusNode != null) { // checks if something is in there
            System.out.println(focusNode);
            preOrderTraverseTree(focusNode.leftChild);
            preOrderTraverseTree(focusNode.rightChild);
        }
    } // end preorder tree traversal

    public void postOrderTraverseTree(Node focusNode) { // post order tree traversal using recursion
        if(focusNode != null) { // checks if something is in there
            postOrderTraverseTree(focusNode.leftChild);
            postOrderTraverseTree(focusNode.rightChild);
            System.out.println(focusNode);
        }
    } // end post order tree traversal

    public Node findNode(int key) { // searches tree by key value
        Node focusNode = root;
        while(focusNode.key != key) {
            if(key < focusNode.key) {
                focusNode = focusNode.leftChild;
            } 
            else {
                focusNode = focusNode.rightChild;
            }

            if(focusNode == null) 
                return null;
        }
        return focusNode;
    } // end tree search by key

    public boolean remove(int key) {
        Node focusNode = root;
        Node parent = root;

        boolean isItAleftChild = true;

        while(focusNode.key != key) {
            parent = focusNode;

            if(key < focusNode.key) {
                isItAleftChild = true;
                focusNode = focusNode.leftChild;
            } else {
                isItAleftChild = false;
                focusNode = focusNode.rightChild;
            }
            if(focusNode == null)
                return false;
        }

        if(focusNode.leftChild == null && focusNode.rightChild == null) {
            if(focusNode == root) {
                root = null;
            } else if(isItAleftChild) {
                parent.leftChild = null;
            } else {
                parent.rightChild = null;
            }
        }
        else if(focusNode.rightChild == null) {
            if(focusNode == root)
                root = focusNode.leftChild;
            else if(isItAleftChild)
                parent.leftChild = focusNode.leftChild;
            else parent.rightChild = focusNode.leftChild;
        }
        else if(focusNode.leftChild == null) {
            if(focusNode == root)
                root = focusNode.rightChild;
            else if(isItAleftChild)
                parent.leftChild = focusNode.rightChild;
            else 
                parent.rightChild = focusNode.leftChild;
        }
        else {
            Node replacement = getRePlacementNode(focusNode);
            if(focusNode == root)
                root = replacement;
            else if(isItAleftChild)
                parent.leftChild = replacement;
            else parent.rightChild = replacement;

            replacement.leftChild = focusNode.leftChild;
        }
        return true;
    }

    public Node getRePlacementNode(Node replacedNode) {
        Node replacementParent = replacedNode;
        Node replacement = replacedNode;

        Node focusNode = replacedNode.rightChild;

        while(focusNode != null) {
            replacementParent = replacement;
            replacement = focusNode;
            focusNode = focusNode.leftChild;
        }

        if(replacement != replacedNode.rightChild) {
            replacementParent.leftChild = replacement.rightChild;
            replacement.rightChild = replacedNode.rightChild;
        }

        return replacement;
    }


    public static void main(String[] args) {
        NewBinaryTree theTree = new NewBinaryTree();
        // insert testing code
    }

}

class Node { // Node class
    int key;
    String name;

    Node leftChild;
    Node rightChild;

    Node(int key, String name) { // node constructor
        this.key = key;
        this.name = name;
    }

    public String toString() { // prints out contents of Nodes
        return name + " has a key " + key;
    }
} // end node class

Answer 1

Many of your comments are superfluous. If you flood your reader with useless comments, they might skip some important ones:

// adds node to tree - this is already clear from method name - addNode.

// end in order tree traversal - markers such as this are unnecessary, if you are using modern IDE. In most editors there are much better ways to easily navigate through your code.

getRePlacementNode should be private. It doesn't look it would be useful to users of your class. This way you will be able to change it without breaking backwards compatibility.

remove(int) is really long. It looks like it could be split up into smaller methods. You should re-use findNode(int) instead of copying it.

I'm not sure if your program works as intended, try:

theTree.addNode(0, "a");
theTree.addNode(1, "b");
theTree.addNode(2, "c");
theTree.remove(1);
theTree.inOrderTraverseTree(theTree.root);

should both 1 and 2 be removed? It's a good idea to add unit tests to your classes. This way, if there is a test checking this behavior, it probably is intended. If not, it's probably a bug.

Answer 2

Many of these methods would be simplified by moving them to Node. The biggest clue is how you have to keep passing Nodes around between the various Tree methods and recursively. This makes Node responsible for managing its key, name, and children while leaving Tree free to worry solely about the root.

// Tree
public Node findNode(int key) {
    return root == null ? null : root.find(key);
}

// Node
public Node find(int key) {
    if (key == this.key) {
        return this;
    }
    else if (key < this.key) {
        return leftChild == null ? null : leftChild.find(key);
    }
    else {
        return rightChild == null ? null : rightChild.find(key);
    }
}

Combining this with the Null Object pattern would simplify others even further. Instead of storing null in the root, left, or right child when there is no key stored there, store a shared instance of NullNode which implements most methods by doing nothing or returning null. Since it doesn't store any data, it can be a static member of Tree shared by all trees.

private static final NullNode NULL = new NullNode();

// Tree
public void preOrderTraverse() {
    root.preOrderTraverse();
}

// Node
public void preOrderTraverse() {
    System.out.println(this);
    leftChild.preOrderTraverse();
    rightChild.preOrderTraverse();
}

// NullNode
public void preOrderTraverse() {
    // nothing to do
}

This eliminates much of the null-checking that complicates code and makes it harder to read and follow and is a common source of bugs.

// Tree
public Node findNode(int key) {
    return root.find(key);
}

// Node
public Node find(int key) {
    if (key == this.key) {
        return this;
    }
    else if (key < this.key) {
        return leftChild.find(key);
    }
    else {
        return rightChild.find(key);
    }
}

// NullNode
public Node find(int key) {
    return null;
}

Using this technique can complicate some logic, for example insert which now must check to see if the node is a real one or not. One trick around this is to have the node return a boolean stating whether it was able to insert the new node or not. If not, overwrite it.

// Tree
public void addNode(int key, String name) {
    Node node = new Node(key, name);
    if (!root.add(node)) {
        root = node;
    }

// Node
public boolean add(Node node) {
    if (node.key == this.key) {
        // Your code doesn't handle a key clash. What should we do?
        throw new IllegalArgumentException("Key clash");
    }
    else if (node.key < this.key) {
        if (!leftChild.add(node)) {
            leftChild = node;
        }
    }
    else {
        if (!rightChild.add(node)) {
            rightChild = node;
        }
    }
    return true;
}

// NullNode
public boolean add(Node node) {
    return false;
}

One thing I definitely don't like is leaking Node outside of Tree. I think findNode should return the node's name instead of the node itself. Node should be a static inner class of Tree and entirely an implementation detail.

Finally, as Banthar said, you need to look again at the case of removing a node with two children. It's hard to tell from the code, but it looks like you drop the right subtree instead of assigning it to the replacement. As well, you should be promoting the right-most (largest) node from the left subtree, yet I see you moving left in getRePlacementNode. A better name for this method might be removeLargestNode since it should be removed from the left subtree.