scarface scarface - 2 months ago 8
Java Question

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.

Answer

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.