Generating a Full Binary Tree Recursively through a Java Method

Question

The method is supposed to take in two parameters one for depth and one for the integer value of the root of the tree. For Example: for any given N, returns the root reference of a full binary search tree of depth N such that the nodes store the integers 1, 2, …, 2 N+1 – 1. I'm struggling to get this right. Here is what I have:

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

           leftChild=BSTFactory(top-1,depth-1);
           rightChild=BSTFactory(top+1,depth-1);
           root=new BinaryNode(rightChild,leftChild,top);
            return root;
       }
       return root;
    }

The method works for 2 base cases which are 0 and 1 for the depth, but it will not work for anything greater. I must be messing something up with the recursion, but I can't seem to figure out what it is. — sudoMan13
– sudoMan13, Commented Oct 29, 2014 at 19:00
Do you know how to use a debugger? You need to simply step through the code and watch what happens. — StilesCrisis
– StilesCrisis, Commented Oct 29, 2014 at 19:13

Eran · Accepted Answer · 2014-10-29 19:54:06Z

First of all, the two parameters of your method depend on each other. For example, BSTFactory(1,3) can't be a full binary tree with a minimal node of 1, since if the root already contains the minimal node, the left sub-tree must be empty (unless you allow negative values in your tree, which is not clear from your question, since you seem to want the tree to store integers starting from 1).

Therefore, I would suggest a wrapper method that would accept only the depth, and calculate the matching root node. We'll see how the two parameters are related later.

Now let's look at some small full binary trees to figure out the recursion :

Depth 0

Depth 1

   2
1     3

Depth 2

     4
   2    6
 1  3  5  7

Depth 3

          8
     4        12
  2     6   10   14
1   3  5 7 9 11 13 15

What can we learn from these examples?

If we are creating a full binary search tree of depth n :

The root would be 2^n
The left sub-tree will be rooted at root - 2^(n-1)
The right sub-tree will be rooted at root + 2^(n-1)

Therefore, the recusion should be :

public static BinaryNode BSTFactory(int root, int depth) 
{
    BinaryNode leftChild,rightChild;
    if (depth==0){
        return new BinaryNode(null,null,root);
    } else {
       leftChild=BSTFactory(root-Math.pow(2,depth-1),depth-1);
       rightChild=BSTFactory(root+Math.pow(2,depth-1),depth-1);
       return new BinaryNode(rightChild,leftChild,root);
   }
}

Note that in order for this to work (i.e. that your minimal node would be 1), you must call the method with a root and depth such that root=2^depth. To ensure that, lets define a wrapper method :

public static BinaryNode BSTFactory(int depth) 
{
    return BSTFactory (Math.pow(2^depth),depth);
}

If you call the two parameter method with arbitrary root and depth, you can get binary trees such as :

BSTFactory (6,1)

     6
   5   7

BSTFactory (1,2)

       1
    -1    3
  -2  0  2  4

There are still full binary trees, but their minimal value is not 1.

Collectives™ on Stack Overflow

Generating a Full Binary Tree Recursively through a Java Method

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related