CODEWITHSUNDEEP
javadata-structuresbinary-tree
sam_rox
sam_rox

Reputation: 747

Inserting an element to a binary tree

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

Upvotes: 1

Views: 6452

Answers (2)

wastl
wastl

Reputation: 2641

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);   //
}

Upvotes: 0

Emanuele Paolini
Emanuele Paolini

Reputation: 10162

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.

Upvotes: 4

Related Questions