How to add nodes in a binary search tree correctly?
This is my code
public boolean insertWord(String key, String meaning) {
if((root == null) ){
root = new TreeNode();
root.key = key;
root.meaning = meaning;
}
else{
TreeNode subroot = root;
if(subroot.key.compareTo(key) == 0){
return false;
}
else if(key.compareTo(subroot.key) < 0){
if(subroot.left != null){
subroot = root.left;
return insertWord(key, meaning);
}
else{
subroot.left = new TreeNode();
subroot.left.key = key;
subroot.left.meaning = meaning;
}
}
else{
if(subroot.right != null){
subroot = root.right;
return insertWord(key, meaning);
}
else{
subroot.right = new TreeNode();
subroot.right.key = key;
subroot.right.meaning = meaning;
}
}
}
return true;
}
Doing this gives me a stackoverflow error. Can someone please help me understand why I keep getting this error. I know it because of the infinite loop, but I don't know why this is happening. Can someone tell me where this is happening and how to fix it? Thanks to
source to share
In the code below, if subroot
installed as root.left
, then shouldn't you use the key subroot
further? Where do you pass this information?
if(subroot.left != null){
subroot = root.left;
return insertWord(key, meaning);
}
Now I present my version, which I have implemented:
protected Node<T> insertValue(T value) {
Node<T> newNode = getNewNode(value);
// If root is null, assign
if (root == null) {
root = newNode;
size++;
return newNode;
}
Node<T> currentNode = root;
while (currentNode != null) {
if (newNode.getData().compareTo(currentNode.getData()) <= 0) { // Less than or equal to goes left
if(currentNode.getLeft() == null) {
insertNodeToLeft(currentNode, newNode);
break;
}
currentNode = currentNode.getLeft();
} else { // Greater than goes right
if (currentNode.getRight() == null) {
insertNodeToRight(currentNode, newNode);
break;
}
currentNode = currentNode.getRight();
}
}
return newNode;
}
Hope this helps you.
As Aaron said, you need to update a new key to which you will compare the following. In your code, if the node field is null you have inserted the node, but if it is not null, you need to compare your key with the key of that new node. Where is this code?
else if(key.compareTo(subroot.key) < 0){
if(subroot.left != null){
subroot = root.left;
// WHERE ARE YOU USING KEY OF THIS NEW NODE subroot FOR COMPARISON?
return insertWord(key, meaning);
}
else{
subroot.left = new TreeNode();
subroot.left.key = key;
subroot.left.meaning = meaning;
}
}
Edit: The implementation of the methods for pasting left and right should be something similar:
private void insertNodeToLeft(Node<T> parent, Node<T> child) {
// New left node
parent.setLeft(child);
child.setParent(parent);
size++;
}
private void insertNodeToRight(Node<T> parent, Node<T> child) {
// New right node
parent.setRight(child);
child.setParent(parent);
size++;
}
source to share