Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive Binary Search Tree Insert

So this is my first java program, but I've done c++ for a few years. I wrote what I think should work, but in fact it does not. So I had a stipulation of having to write a method for this call:

tree.insertNode(value);

where value is an int. I wanted to write it recursively, for obvious reasons, so I had to do a work around:

public void insertNode(int key) {
    Node temp = new Node(key);

    if(root == null) root = temp;

    else insertNode(temp);
}

public void insertNode(Node temp) {
    if(root == null)
        root = temp;

    else if(temp.getKey() <= root.getKey())
        insertNode(root.getLeft());

    else insertNode(root.getRight());
}

Thanks for any advice.

like image 719
Nick Sinklier Avatar asked Feb 12 '13 04:02

Nick Sinklier


People also ask

How do you insert it in BST iteratively?

Iterative Method To insert the node into the binary search tree, we need to compare the node with the tree's root. If the node is greater than the root value, we move to the right side of the binary search tree; otherwise, we move to the left side of the binary search tree.

Which type of recursion is used in binary search tree?

The recursive put() method accomplishes this task using logic similar to that we used for the recursive search: If the tree is empty, we return a new node containing the key and value; if the search key is less than the key at the root, we set the left link to the result of inserting the key into the left subtree; ...


1 Answers

// In java it is little trickier  as objects are passed by copy.
// PF my answer below.

// public calling method

public void insertNode(int key) {
    root = insertNode(root, new Node(key));
}

// private recursive call

private Node insertNode(Node currentParent, Node newNode) {

    if (currentParent == null) {
        return newNode;
    } else if (newNode.key > currentParent.key) {
        currentParent.right = insertNode(currentParent.right, newNode);
    } else if (newNode.key < currentParent.key) {
        currentParent.left = insertNode(currentParent.left, newNode);
    }

    return currentParent;
}

Sameer Sukumaran

like image 151
user2986935 Avatar answered Sep 17 '22 13:09

user2986935