Forum Stats

  • 3,727,349 Users
  • 2,245,373 Discussions
  • 7,852,749 Comments

Discussions

Binary Search Tree insertion & inorder

User_AYF65
User_AYF65 Member Posts: 135 Red Ribbon
edited April 2016 in New To Java

Hi,

I have written a program to insert values in a binary search tree and print the values using inorder traversal. Following is my code:

class TreeNode{

   int data;

   TreeNode left;

   TreeNode right;

   TreeNode(int data1, TreeNode l, TreeNode r){

      data = data1;

      left = l;

      right =r;

   }

}

class bst1{

   TreeNode root;

   bst1( ) {

      root = null;

   }

 

   public static void main(String[ ] args){

       

        bst1 obj = new bst1();

  int[ ] arr= {90, 75, 10, 20, 30, 40, 50, 70};

        for(int i=0; i<8; ++i)

        obj.root= obj.insert(arr[i], obj.root);

        obj.inorder (obj.root);

   }

   TreeNode insert(int data, TreeNode t){

      if(t ==null) {

         t = new TreeNode(data, null, null);

      }

      else if(t.data<data){

         t.right = insert(t.data, t.right);

      }

      else

         t.left = insert(t.data, t.left);

      return t;

  }

    private void inorder(TreeNode r)

  {

  if(r !=null)

  {

  inorder(r.left);

  System.out.print(r.data +" ");

  inorder(r.right);

  }

       }

}


Can somebody please guide me what's the problem with my code. Its printing only the first node.

>javac bst1.java

>java bst1

90 90 90 90 90 90 90 90

>

Zulfi.

Answers

  • TPD-Opitz
    TPD-Opitz Member Posts: 2,465 Silver Trophy
    edited April 2016

    Thanks for Posting an SSCCE.

    The problem is here:

    TreeNode insert(int data, TreeNode t) {
            if (t == null) {
                t = new TreeNode(data, null, null);
            } else if (t.data < data) {
                t.right = insert(t.data, t.right);
            } else {
                t.left = insert(t.data, t.left);
            }
            return t;
        }
    

    You pass the data of the parent node instead of the new value to the child creation.

    better is this

    TreeNode insert(int data, TreeNode t) {
            if (t == null) {
                t = new TreeNode(data, null, null);
            } else if (t.data < data) {
                t.right = insert(data, t.right);
            } else {
                t.left = insert(data, t.left);
            }
            return t;
        }
    

    And the best solution was to choose meaningfull names for your identifiers:

    TreeNode appendNewNode(int newData, TreeNode currentNode) {
            if (currentNode == null) {
                currentNode = new TreeNode(newData, null, null);
            } else if (currentNode.data < newData) {
                currentNode.right = appendNewNode(newData, currentNode.right);
            } else {
                currentNode.left = appendNewNode(newData, currentNode.left);
            }
            return currentNode;
        }
    

    bye

    TPD

This discussion has been closed.