CODEWITHSUNDEEP
javabinary-search-tree
Nick Sinklier
Nick Sinklier

Reputation: 221

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.

Upvotes: 7

Views: 58726

Answers (5)

L01c
L01c

Reputation: 1063

You should have a look to this article. It helps to implement a tree structure and search, insert methods: http://quiz.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

// This method mainly calls insertRec()
void insert(int key) {
   root = insertRec(root, key);
}

/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {

    /* If the tree is empty, return a new node */
    if (root == null) {
        root = new Node(key);
        return root;
    }

    /* Otherwise, recur down the tree */
    if (key < root.key)
        root.left = insertRec(root.left, key);
    else if (key > root.key)
        root.right = insertRec(root.right, key);

    /* return the (unchanged) node pointer */
    return root;
}

Upvotes: 2

user2986935
user2986935

Reputation: 181

// 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

Upvotes: 18

Arkanoid
Arkanoid

Reputation: 373

The code looks a little confusing with overloaded functions. Assuming member variables 'left' and 'right' to be the left child and right child of the BSTree respectively, you can try implementing it in the following way:

 public void insert(Node node, int value) {
    if (value < node.value)
    {
        if (node.left != null)
        {
            insert(node.left, value);
        } 
        else
        {     
            node.left = new Node(value);
        }
    } 
    else if (value > node.value)
    {
        if (node.right != null)
        {
            insert(node.right, value);
        }
        else
        {
            node.right = new Node(value);
        }
    }
}

........
public static void main(String [] args)
{ 
     BSTree bt = new BSTree();
     Node root = new Node(100);
     bt.insert(root, 50);
     bt.insert(root, 150);
}

Upvotes: 3

user000001
user000001

Reputation: 33317

but where is temp when you insertNode?? With your current implementation temp is lost if root is not null.

I think you want something like 

root.getLeft().insertNode(temp);

and 

root.getRight().insertNode(temp);

i.e. To insert the new Node (temp) to either the left or the right subtree.

Upvotes: 0

Bimalesh Jha
Bimalesh Jha

Reputation: 1504

You can use standard Integer (wrapper for primitive int) object instead of creating a new object type Node. On latest java Integer/int auto-boxing is supported. Hence your method insertNode(int key) can take in Integer argument too (ensure it is not null).

EDIT: Pls ignore above comment. I did not understand your real question. You will have to overload insertNode(). I think you are right.

Upvotes: 0

Related Questions