Inserting an element to a binary tree

Question

This is my implementation of binary Node class:

public class BinaryNode{
    int element;
    BinaryNode left;
    BinaryNode right;
    BinaryNode(int theElement,BinaryNode lt,BinaryNode rt){
        element=theElement;
        left=lt;
        right=rt;       
    }
    BinaryNode(int theElement){
        this(theElement,null,null);
    }

}

Here's my insert method in binaryTree class

public class BinaryTree {
    private BinaryNode root;

    public BinaryTree(){
        root= null;
    }
    BinaryTree(int nodeValue){
        root=new BinaryNode(nodeValue);

    }
public void insert(BinaryNode node,int x){
        if(node==null){
            node=new BinaryNode(x);
        }
        else if(node.element<x){
            insert(node.left,x);
        }
        else if (node.element>x){
            insert(node.right,x);
        }
        else
            System.out.println("Duplicates not allowed");
    }

I have two questions.
1) how can I insert elements to this BinaryTree class and thereby create a tree.

public static void main (String args[]){
        BinaryTree t=new BinaryTree();
        t.insert(t.root,5);
        }

But after inserting 5 how can I call on insert method to add integers like 10,12,78,...

2) Also when I looked up at some code for inserting to binary trees I found this code .

/** 
   Inserts the given data into the binary tree. 
   Uses a recursive helper. 
  */ 
  public void insert(int data) { 
    root = insert(root, data); 
  } 


  /** 
   Recursive insert -- given a node pointer, recur down and 
   insert the given data into the tree. Returns the new 
   node pointer (the standard way to communicate 
   a changed pointer back to the caller). 
  */ 
  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); // in any case, return the new pointer to the caller 
  }

The code looks similar to mine, but why use a helper method insert() as well?What's the purpose of it?
Can someone please solve help me to understand this

Emanuele Paolini · Accepted Answer · 2014-05-24 16:03:01Z

4

Inserting an element in a binary tree should require only the tree and the element as input. The tree itself should determine which node should be updated. This is achieved by means of a recursive function which starts from root: this is the helper function, which acts on a node.

answered May 24, 2014 at 16:03

Emanuele Paolini

10.2k5 gold badges45 silver badges69 bronze badges

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

Comments

wastl · Accepted Answer · 2014-05-24 16:03:07Z

The first problem is that you won't be able to access t.root directly because it's private. You either need a getter

public BinaryNode getRoot() {
    return this.root;
}

or make root public

The helper method is used, so the new root of the BinaryTree can be determined. And because the root should not be returned to the caller. But since it's easier to insert something into a binary tree recursivley the private method is used to do that. You would use the methods like this:

public static void main(String[] args) {
    BinaryTree t = new BinaryTree(5); //Create a new tree with one item
    t.insert(12); // Assuming that you used the implementation with the helper method
    t.insert(3);  //

    t.insert(t.getRoot(),12);  // Assuming you used your implementation
    t.insert(t.getRoot(),3);   //
}

I didn't have to declare root as public.The problem I wasn't setting the root node.When I did like t.root=t.insert(t.root,5); t.insert(t.root,6); t.insert(t.root,4); t.insert(t.root,60); t.insert(t.root,25); it worked fine

Collectives™ on Stack Overflow

Inserting an element to a binary tree

2 Answers 2

Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Related