Inserting new Node in a Binary Search Tree

Posted on

Problem

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);
    }
}

Solution

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.

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);
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *