CODEWITHSUNDEEP
javaoutputbinary-search-tree
Gizzle
Gizzle

Reputation: 3

Binary Search Tree in java, Inorder traversal is only recognizing a single number in the tree

Not sure where my mistake might be but I fell as though it is somewhere in search or insert. 

private boolean search( Node<T> subtree, T key)

I feel like this is where I need to change things. Maybe private boolean search*( Node subtree, T key)* instead but how could I go about this when doing the comparison?

public class BST< T extends Comparable< T >> {
private Node< T > root;

  public BST() {
    this.root = null;
  }

      public int height() {
    return height( this.root );


    if( subtree == null ) {
  return 0;
} else {
  return 1 + Math.max( height( subtree.left ), height( subtree.right ) );
}
  }

   public void insert( T data ) {
if( this.root == null ) {
  this.root = new Node( data );
} else {
  insert( this.root, data );
}
 }

  private void insert( Node <T> subtree, T data ) {
if( data.compareTo( subtree.data ) < 0 ) {
  if( subtree.left == null ) {
    subtree.left = new Node( data );
  } else {
    insert( subtree.left, data );
  }
} else {
  if( subtree.right == null ) {
    subtree.right = new Node( data );
  } else {
    insert( subtree.right, data );
  }
}
     }

  public boolean delete( T data ) {
return false;
    }

  public boolean search( T key ) {
return search( this.root, key );
  }

  private boolean search( Node<T> subtree, T key) {
/* YOU IMPLEMENT THIS */    
if(subtree.data == null) {
    return false; 
  } else  {
if( key == subtree.data ) {
    return true;
} else {
    if(key.compareTo( subtree.data ) < 0 ) {
        return search(subtree.left, key);
    } else {
        return search(subtree.right,key);
        }
     }    
   }
}

 public void inorder() {
inorder( this.root );
 }

  private void inorder( Node subtree ) {
/* YOU IMPLEMENT THIS
  inorder traversal of subtree->left
  print out subtree->data
  inorder traversal of subtree->right
*/

    if(subtree != null) {
    inorder(subtree.left);
    System.out.println(root.data + " ");
    inorder(subtree.right); 
  }
  }


  public void preorder() {
preorder( this.root );
   }

      private void preorder( Node subtree ) {
/* YOU IMPLEMENT THIS */
if(subtree != null){
    System.out.println(subtree.data + "");
    preorder(subtree.left);
    preorder(subtree.right);
}
   }

  public void postorder() {
postorder( this.root );
}

  private void postorder( Node subtree ) {
/* YOU IMPLEMENT THIS */
if(subtree != null){
   postorder(subtree.left);
   postorder(subtree.right);
   System.out.println(subtree.data + "");
}

  }

  // public String toString() {
  //   StringBuilder builder = new StringBuilder();
  //
  //
  //
 //   return builder.toString();
  // }

  public static void main( String[] args ) {
BST<Integer> tree = new BST<>();

tree.insert( 29 );
tree.insert( 17 );
tree.insert( 50 );
tree.insert( 5 );
tree.insert( 20 );
tree.insert( 30 );
tree.insert( 100 );

System.out.println( "Tree height is: " + tree.height() );

System.out.println( "Inorder traversal:" );
tree.inorder();

System.out.println( "Preorder traversal:" );
tree.preorder();

System.out.println( "Postorder traversal:" );
tree.postorder();
  }

  private class Node< T > {
private T data;
private Node left;
private Node right;

    public Node( T data ) {
  this( data, null, null );
}

   public Node( T data, Node left, Node right ) {
  this.data = data;
  this.left = left;
  this.right = right;
    }
 }
}

What's printed out.

Tree height is: 3

Inorder traversal:
29 
29 
29 
29 
29 
29 
29 

Preorder traversal:
29
17
5
20
50
30
100

Postorder traversal:
5
20
17
30
100
50
29

Upvotes: 0

Views: 96

Answers (2)

Vikram
Vikram

Reputation: 333

In your inorder method, you are always printing the root node, instead of the node you are currently at.

Instead of:

System.out.println(root.data + " ");

you should use:

System.out.println(subtree.data + " ");

Upvotes: 1

liushui
liushui

Reputation: 27

replace root with subtree in inorder method otherwise it will output the data of root every time, maybe it is your Wrong hands.

private void inorder( Node subtree ) {
    if(subtree != null) {
        inorder(subtree.left);
        System.out.println(subtree.data + " ");/////replace root with subtree
        inorder(subtree.right); 
    }
}

Upvotes: 1

Related Questions