CODEWITHSUNDEEP
javarecursionbinary-search-tree
Iva
Iva

Reputation: 101

Creating a Binary Search Tree recursively in Java

I've been trying to create a recursive method that will create a full binary search tree. This method returns a reference to the root of this tree. As parameters I'm passing the depth of the tree as well as the number stored in the root of the current subtree. I have managed to work the solution for the 2 base cases, when the depth is 0 and 1, however when I try it for a number greater then 1 then I only get level 0 and level 1 instantiated correctly but not the next one. Any help would be great

public class BinaryNode {
private int data;
private BinaryNode left, right;

public BinaryNode(int initialData, BinaryNode initialLeft,
        BinaryNode initialRight) {
    data = initialData;
    left = initialLeft;
    right = initialRight;
}
   public static BinaryNode BSTFactory(int top,int depth) {
    BinaryNode root=new BinaryNode(top,null,null);
    BinaryNode leftChild,rightChild;
    if(depth==0)
        //return root;
    if(depth==1){
        //create 2 children left and right
        leftChild=new BinaryNode(top-1,null,null);
        rightChild=new BinaryNode(top+1,null,null);
        root=new BinaryNode(top,leftChild,rightChild);
        //return root;
    }
    if(depth>1){

        leftChild=BSTFactory(top-1,depth-1);
        rightChild=BSTFactory(top+1,depth-1);
        root=new BinaryNode(top,leftChild,rightChild);
        //return root;
    }
    return root;
}
   public class Applications {

public static void main(String[] args){
    BinaryNode root2=BinaryNode.BSTFactory(8, 2);
System.out.println(root2.toString());


   }

}

  This is the output:
  data: 8
  8's left: data: 7
  7's left: null
  7's right: null
  8's right: data: 9
  9's left: null
  9's right: null

Upvotes: 0

Views: 1415

Answers (1)

Judge Mental
Judge Mental

Reputation: 5239

When the empty tree is represented by null, there is usually no need for more than one base case.

public class BinaryNode {
    public static BinaryNode bstFactory( int data, int depth ) {
        if ( depth >= 31 )
            throw new IllegalArgumentException( "too deep for integer data" );
        else if ( depth < 0 )
            throw new IllegalArgumentException( "non-sensical depth" );
        return ( depth == 0 )
            ? null
            : new BinaryNode(
                data,
                bstFactory( data - ( 1 << depth ), depth - 1 ),
                bstFactory( data + ( 1 << depth ), depth - 1 )
            );
    }
    BinaryNode( int data, BinaryNode left, BinaryNode right ) { /*...*/ }
}

Upvotes: 1

Related Questions