CODEWITHSUNDEEP
javarecursionbinary-search-tree
scarface
scarface

Reputation: 584

Java BST recursion

I have recently moved from C++ to Java and now I am playing with data structures which in C++ needed usage of pointers.

I am creating BST in Java now and I used recursion for inserting into Tree and it is not working as I would expect. This code stores only a Node with val = 5. Can you give me any advice?

public class Main
{
    public static void main( String [] args )
    {
      BST<Integer> bst = new BST<Integer>();
      bst . add( 5 );
      bst . add( 10 );
    }
}

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

    private class Node
    {
      private T val;
      private Node left;
      private Node right;

      Node(T val)
      {
        this . val = val;
        left = null;
        right = null;
      }
    }


    public BST()
    {
      root = null;
    }

    public BST( T val )
    {
      root = new Node( val );
    }

    public void add( T val )
    {
      if( root == null )
        root = new Node(val);
      else
        add( root, val );
    }

    private void add( Node parent, T val )
    {
      if( parent == null )
        parent = new Node(val);
      else if( val . compareTo( parent . val ) < 0 )
        add( parent . left, val );
      else if( val . compareTo( parent . val ) > 0 )
        add( parent . right, val );
    }
}

Thank you.

Upvotes: 1

Views: 79

Answers (1)

OldCurmudgeon
OldCurmudgeon

Reputation: 65793

Java is pass-by-reference so doing parent = new Node(val) achieves nothing. You are merely changing the local parameter.

You need to do something like if ( left == null ) left = new Node(val) else add (left,val).

Not posting code because this is likely to be a homework question.

Upvotes: 1

Related Questions