8
\$\begingroup\$

I wrote my own version of a search binary tree in Java. Could someone kindly review it?

public class Tree {

    private Node root;

    public Node find(int id) {

        Node current = root;

        while(current != null) {

            if (current.getId() == id)

                // Node found
                return current;

            current = goNextChild(current, id);
        }

        return current;
    }

    public void insert(int id, String name) {

        Node node = new Node(id, name);

        if (root == null)
            root = node;
        else {

            Node current = root;
            while(current != null) {

                if (current.getId() == id) {
                    // If present, just change information of the current node
                    current.setId(id);
                    current.setName(name);
                    return;
                }
                else if (current.getId() < id) {
                    // Go to the right child
                    if (current.getRightChild() == null) {
                        // If the right child is not present set the new node
                        current.setRightChild(node);
                        return;
                    }
                    else {
                        current = current.getRightChild();
                    }
                }
                else if (current.getId() > id) {
                    // go to the left child
                    if (current.getLeftChild() == null) {
                        // If the left child is not present set the new node
                        current.setLeftChild(node);
                        return;
                    }
                    else {
                        current = current.getLeftChild();
                    }
                }
            }   
        }
    }

    public void delete(int id) {

        Node delNode = find(id);
        Node parent = findParent(delNode);

        if((delNode.getLeftChild() == null)
                && (delNode.getRightChild() == null)) {

            // Delete node with no children

            if (delNode == root)
                root = null;
            else if(parent.getLeftChild() == delNode)
                parent.setLeftChild(null);
            else if(parent.getRightChild() == delNode)
                parent.setRightChild(null);
        }
        else if(delNode.getLeftChild() == null) { 

            // Delete node with one child

            if (delNode == root)
                root = delNode.getRightChild();
            else if(parent.getLeftChild() == delNode)
                parent.setLeftChild(delNode.getRightChild());
            else if(parent.getRightChild() == delNode)
                parent.setRightChild(delNode.getRightChild());
        }
        else {

            // Delete node with two children

            Node successor = produceSuccessor(delNode);

            if (delNode == root)
                root = successor;
            else if(parent.getLeftChild() == delNode)
                parent.setLeftChild(successor);
            else if(parent.getRightChild() == delNode)
                parent.setRightChild(successor);            
        }
    }

    public Node findParent(Node node) {

        Node current = root;

        while(current != null) {

            if (isParent(current, node))
                return current;

            current = goNextChild(current, node.getId());
        }

        return null;
    }

    public void traverse() {
        inOrderTraverse(root);
    }

    private void inOrderTraverse(Node node) {
        if (node != null) {
            inOrderTraverse(node.getLeftChild());
            System.out.print(node.getId() + " ");
            inOrderTraverse(node.getRightChild());
        }

    }

    private Node produceSuccessor(Node node) {

        // Go to the right only once
        Node successor = node.getRightChild();

        if (successor.getLeftChild() == null) {
            // If the right child has no left child, then
            // Some re-connections are needed
            successor.setLeftChild(node.getLeftChild());
        } 
        else {

            // Go to the left multiple times
            while (successor.getLeftChild() != null) {
                successor = successor.getLeftChild();
            }

            findParent(successor).setLeftChild(null);
            successor.setLeftChild(node.getLeftChild());
            successor.setRightChild(node.getRightChild());
        }

        return successor;       
    }

    private Node goNextChild(Node node, int id) {
        if (node.getId() < id)
            // Go to the right child
            return node.getRightChild();
        else
            // go to the left child
            return node.getLeftChild();
    }

    private boolean isParent(Node parent, Node child) {

        if (parent == null || child == null)
            return false;

        if (parent.getLeftChild() != null &&
            parent.getLeftChild().getId() == child.getId())
            return true; // child is left node

        if (parent.getRightChild() != null &&
                parent.getRightChild().getId() == child.getId())
                return true; // child is right node

        return false;
    }
}

public class TreeData {

    private int id;
    private String name;

    public TreeData(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
}

public class Node {

    private TreeData data; // Don't return this, see Demeter law
    private Node leftChild;
    private Node rightChild;

    public Node(int id, String name) {
        data = new TreeData(id, name);
    }

    public Node getLeftChild() {
        return leftChild;
    }
    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }
    public Node getRightChild() {
        return rightChild;
    }
    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }   
    public int getId() {
        return data.getId();
    }
    public void setId(int id) {
        data.setId(id);
    }
    public String getName() {
        return data.getName();
    }
    public void setName(String name) {
        data.setName(name);;
    }
}

public class App {

    public static void main(String[] args) {

        Tree tree = new Tree();

        tree.insert(3, "Albert");
        tree.insert(1, "Roby");
        tree.insert(4, "Jack");
        tree.insert(8, "Ron");
        tree.insert(11, "Black");
        tree.insert(9, "Bob");
        tree.insert(7, "Bongo");

        tree.traverse();        
        System.out.println("");

        tree.delete(4);
        tree.traverse();
        System.out.println("");

        tree.delete(8);
        tree.traverse();
        System.out.println("");

        tree.delete(3);
        tree.traverse();
        System.out.println("");

        tree.delete(1);
        tree.traverse();
        System.out.println("");

        tree.delete(7);
        tree.traverse();
        System.out.println("");

        tree.delete(9);
        tree.traverse();
        System.out.println("");

        tree.delete(11);
        tree.traverse();
    }
}
\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

Design

  1. I highly recommend that you create a Tree interface that can be implemented by a BinarySearchTree class. Take your insert, delete, find, etc. methods and declare them over there. Suppose you decide to create a Red-Black tree, then you could create a RedBlackTree class which implements the same interface. This makes swapping out implementations very easy! Here's a good link to read: Why would a programmer want to separate implementation from interface?
  2. Why do you need the TreeData class? If you ask yourself "What is a node in a tree and what does it do?", then your POJO should reflect that answer. In this case, a tree node has a key, a value (or some piece of data), a left child, and a right child. Why shouldn't the Node represent this itself? Sure, you don't need to expose setter methods for each attribute, but by adding getter methods on Node, you're still exposing the attributes indirectly.

Correctness

  1. Take a look at your find() method. Currently, if the Node you're searching for doesn't exist, you return the root of the tree. Is that really what you want to do? I would either return null, or take a look at the Optional documentation (would recommend going this route as it's a good way to help avoid null pointer exceptions!).

Minor Notes

  1. Make variables final when possible. It'll make your code less error-prone and is just general good-practice.
  2. Take a look at your 'if-else' statements, and you'll notice you've got some cases where you have 'if, else if, else if'. I highly recommend following a conventional 'if, else if, else' pattern to prevent bugs in the code. If you need to, add some documentation to clarify the branches.
\$\endgroup\$
2
\$\begingroup\$

Insert:

Your insert operation is a bit overcomplicated.

  1. Your last outer else if is redundant a plain else would suffice.
  2. Your nested ifs are unnecessary IMO a more readable way would be to keep track of the parent and after the loop terminates add the new node.

Delete:

You have to much code repetition for example you use this several times

        if (delNode == root)
            root = delNode.getRightChild();
        else if(parent.getLeftChild() == delNode)
            parent.setLeftChild(delNode.getRightChild());
        else if(parent.getRightChild() == delNode)
            parent.setRightChild(delNode.getRightChild());

You should abstract this into a function.


This first if:

if((delNode.getLeftChild() == null)
                && (delNode.getRightChild() == null)) 

Can be change to this:

if(delNode.getRightChild() == null)

And put the same code as the fist if changing getRightChild() to getLeftChild(). You code would end up in the third case even when delNode.getRightChild() is null and delNode.getLeftChild() is not.


Finally you are traversing the tree 2 times for finding the parent and the node, which even though it doesn't change the asymptotic running time its unnecessary.


Node class

I would make your class nested. Also Node is an implementation detail so it should be private. I would omit the setters method as well because in this particular case you wont need to do any additional operations or validations.


Comments

Your comments are completely worthless. You should comment your code only if it does help or for API documentation. But in general you should let the code speak for itself.


Additional notes:

Apart from what TheDesertMonk said you can use generics for your map. There are more things that can be improved but I need to sleep ;).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.