how to add nodes in binary search tree properly?

Question

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 stackoverflow error. Can someone please help me understand why I keep getting that error. I know its because of an infinite loop but I dont know why its happening. Can someone tell me where it is happening and how to fix it? Thanks

your function never goes out of the root node. note that assignment to subroot only changes a local variable which is never passed to the recursive call. — Diego
– Diego, Commented May 2, 2015 at 4:37

user4856076 · Accepted Answer · 2015-05-02 04:44:50Z

2

In the below code if subroot is set as root.left then shouldn't you use the key of subroot further? Where are you passing that information?

if(subroot.left != null){
       subroot = root.left;
       return insertWord(key, meaning);
 }

Now I am presenting 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 it will help you.

answered May 2, 2015 at 4:44

user4856076

Sign up to request clarification or add additional context in comments.

1 Comment

user2775042 Over a year ago

Hi, Can you please show me how insertNodetoLeft/insertNodetoRight method looks like for this to work? Thanks

akhil_mittal · Accepted Answer · 2015-05-03 02:14:58Z

1

As Aaron has pointed out you need to update the new key to which you will compare next. In your code if left node is null you inserted the node but if it is not null then you need to compare your key with the key of this 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 for methods to insert 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++;
}

edited May 3, 2015 at 2:14

answered May 2, 2015 at 4:50

akhil_mittal

24.3k8 gold badges99 silver badges97 bronze badges

1 Comment

user2775042 Over a year ago

wouldnt it recursively check it in if(subroot.key.compareTo(key) == 0){ return false; } Since return insertword(,key,meaning) is called

Collectives™ on Stack Overflow

how to add nodes in binary search tree properly?

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related