Insert Into a Binary Tree in Java

[Akino877]

Hello,

I am new to Java and have a question I wonder if someone could please help?
I have the following code to insert into a binary tree :

public void insert(int data) {
      root = insert (root,data);
}

/* recursive helper */
private Node insert(Node node, int data) {
      if (node == null)
            node = new Node(data);
      else if (data < node.data)
            node.left = insert(node.left, data);
      else
            node.right = insert(node.right, data);
      return (node);
}

I walked through this code and saw that when insert(Node node, int data) finally
returned from the recursion, it returned the node it just created and thus it
replaced the value of "root". But when I inserted some debugging statements to
print out the "data" of "root", I saw that the "data" of "root" never changed, which
was correct (and expected result).

I wonder if someone could tell me why the value of "root" never changed when
everytime insert(Node node, int data) was called, it returned a new "node".

Thank you very much in advance,

Akino

[liuzhi0210]

The key to understand why this does not work problem is to know that Java passes objects as references and those references are passed by value.

In first function call to "Node insert(Node node, int data)";
The node is a copy of the root, and any changes made on node, only affect the temporary node variable.
The root is not affected.

http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value

[us hosting]

Also, you need to move node to left or right to make the recursion work.

[Sherin]

Try This Code

public class BinarytreeInsert {

    public static void main(String[] args) {
        new BinarytreeInsert().run();
    }

    static class Node {

        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public void run() {
        Node rootnode = new Node(25);
        System.out.println("Building tree with root value " + rootnode.value);
        System.out.println("=================================");
        insert(rootnode, 11);
        insert(rootnode, 15);
        insert(rootnode, 16);
        insert(rootnode, 23);
        insert(rootnode, 79);

    }
    

    public void insert(Node node, int value) {
        if (value < node.value) {
            if (node.left != null) {
                insert(node.left, value);
            } else {
                System.out.println("  Inserted " + value + " to left of Node " + node.value);
                node.left = new Node(value);
            }
        } else if (value > node.value) {
            if (node.right != null) {
                insert(node.right, value);
            } else {
                System.out.println("  Inserted " + value + " to right of Node " + node.value);
                node.right = new Node(value);
            }
        }
    }
}

Output of the program

  Building tree with root value 25
=================================
  Inserted 11 to left of Node 25
  Inserted 15 to right of Node 11
  Inserted 16 to right of Node 15
  Inserted 23 to right of Node 16
  Inserted 79 to right of Node 25