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