CODEWITHSUNDEEP
javabinary-search-tree
jwkoo
jwkoo

Reputation: 2663

binarysearch tree tree.root returns null

I found binary search tree insertion java code on the website,

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

and part of the code is like below,

    if (root == null) { 
        root = new Node(key); 
        return root; 
    }

and I thought we don`t need any return statement because root itself is reference type(Node), so updating root is enough.

so I changed the code like this.

class BinarySearchTree {

class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

Node root;

BinarySearchTree() {
    root = null;
}

void insert(int key) {
    insertRec(root, key);
}

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

    if (root == null) {
        root = new Node(key);
    }

    if (key < root.key)
        insertRec(root.left, key);
    else if (key > root.key)
        insertRec(root.right, key);
}

// Driver Program to test above functions 
public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree(); 

    tree.insert(50);
    tree.insert(20);

    System.out.println(tree.root);
    }
}

but tree.root returns null.

why is this happening?

Upvotes: 0

Views: 779

Answers (4)

VincentxH
VincentxH

Reputation: 9

In your constructor you don't initialise a rootNode. Your key is also not transformed in a Node and you don't set your inserted Node to a left or right node. Also you don't do anything with a node that is equal to the current node you traverse.

Upvotes: -1

Huy Nguyen
Huy Nguyen

Reputation: 2061

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

    if (root == null) {
        root = new Node(key);
    }    
}

It is called "shadows effect".

That mean your root note from parent class is shadowed by root node in your method. To fixed it use "this.root" to reference to parent class and initialized the object.

More information : read "Shadowing" in the article. It explained very well.

http://ocpj8.javastudyguide.com/ch03.html

Upvotes: 0

suvojit_007
suvojit_007

Reputation: 1728

Like others already have pointed out, you need to update your root every time you insert an element.

Just return the value of root and update your global root for the tree.

Node insertRec(Node root, int key) {

    if (root == null) {
        root = new Node(key);
        return root;
    }

    if (key < root.key)
        root.left = insertRec(root.left, key);
    else
       root.right  = insertRec(root.right, key);

   return root;
}

Finally, update your global root.

tree.root = tree.insert(50);
    tree.root = tree.insert(20);

Full code:

class BinarySearchTree {

class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

Node root;

BinarySearchTree() {
    root = null;
}

 Node insert(int key) {
   return insertRec(root, key);
}

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

    if (root == null) {
        root = new Node(key);
        return root;
    }

    if (key < root.key)
        root.left = insertRec(root.left, key);
    else
       root.right  = insertRec(root.right, key);

   return root;
}

// Driver Program to test above functions 
public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree(); 

    tree.root = tree.insert(50);
    tree.root = tree.insert(20);

    System.out.println(tree.root.key);
    }
}

Upvotes: 0

Eran
Eran

Reputation: 394146

root = new Node(key); updates a local variable, it doesn't update the root of the tree (this.root), and it shouldn't. Therefore this assignment doesn't update the tree.

When you return the newly created Node (as in the original code that you changed did), you can assign it to be either the root of the tree (as the original code did with root = insertRec(root, key);) or the left or right child of an existing tree node (as the original code did with root.left = insertRec(root.left, key); or root.right = insertRec(root.right, key);). That's how the tree is updated.

EDIT: Java is a pass by value language, not pass by reference. When you pass a variable to a method, that method can't change the value of the passed variable. If you pass a variable whose value is null to a method, and that method assigns a value to it, the variable will still contain null once the method returns.

Upvotes: 3

Related Questions