current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

I wrote this method to recursively insert a new node at the proper position in a BST. Is it good enough? Can it be improved? It went through a couple of revisions and I still am not very confident in this version. Making the new node root when no nodes are present is taken care of in a separate wrapper function.

public void insertNode(Node<Integer> currentParent, Node<Integer> newNode) {
    if (newNode.getNodeData() < currentParent.getNodeData()) {
        if(currentParent.getLeftChild() == null)
            currentParent.setLeftChild(newNode);
        else
            insertNode(currentParent.getLeftChild(), newNode);

    } else {
        if(currentParent.getRightChild() == null)
            currentParent.setRightChild(newNode);
        else
            insertNode(currentParent.getRightChild(), newNode);
    }
}
share|improve this question

2 Answers 2

up vote 3 down vote accepted

A BST must not contain duplicate values. Your implementation allows inserting a duplicate value as the right child. It should be something like this:

if (newNode.getNodeData() < currentParent.getNodeData()) {
    if (currentParent.getLeftChild() == null) {
        currentParent.setLeftChild(newNode);
    } else {
        insertNode(currentParent.getLeftChild(), newNode);
    }
} else if (newNode.getNodeData() > currentParent.getNodeData()) {
    if (currentParent.getRightChild() == null) {
        currentParent.setRightChild(newNode);
    } else {
        insertNode(currentParent.getRightChild(), newNode);
    }
} else {
    // duplicate item
    // option 1: do nothing: ignore input, add nothing to the tree
    // option 2: throw new IllegalArgumentException("no no: dupe")
}

It's also recommended to use braces always, so I modified the original code accordingly.

share|improve this answer
    
Thanks for pointing that out! –  Nash Vail May 20 at 4:43
up vote 1 down vote

If you use a getter twice or more, save it's value in a varialbe. So I would change your code like that to improve it's performance:

public void insertNode(Node<Integer> currentParent, Node<Integer> newNode) {
    if (newNode.getNodeData() < currentParent.getNodeData()) {
        Node<Integer> currentParentLeftChild = currentParent.getLeftChild();
        if(currentParentLeftChild == null)
            currentParent.setLeftChild(newNode);
        else
            insertNode(currentParentLeftChild, newNode);
    } else {
        Node<Integer> currentParentRightChild = currentParent.getRightChild();
        if(currentParentRightChild == null)
            currentParent.setRightChild(newNode);
        else
            insertNode(currentParentRightChild, newNode);
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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