1
\$\begingroup\$

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);
    }
}
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
0
1
\$\begingroup\$

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);
    }
}
\$\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.