OutOfMemoryError creating a tree recursively?

Question

 root = new TreeNode(N);
 constructTree(N, root);

 private void constructTree(int N, TreeNode node) {
    if (N > 0) {
        node.setLeft(new TreeNode(N-1));
        constructTree(N-1, node.getLeft());
    }
    if (N > 1) {
        node.setMiddle(new TreeNode(N-2));
        constructTree(N-2, node.getMiddle());
    }
    if (N > 2) {
        node.setRight(new TreeNode(N-3));
        constructTree(N-3, node.getRight());
    }

Assume N is the root number, and the three will create a left middle right node of N-1, N-2, N-3.

EX:

etc.

My TreeNode class has the following variables:

private int number;
private TreeNode left, middle, right;

Whenever I construct a tree with an integer greater than 28, I get a OutOfMemoryError. Is my recursive method just incredibly inefficient or is this natural? Thanks!

When N is 29, the resulting tree should have 16.8 million nodes. Since you haven't shown us TreeNode, I don't know how many bytes each node has; but I can't really see it causing you a problem. What do you have your heap size set to? — Dawood ibn Kareem
– Dawood ibn Kareem, Commented Nov 4, 2013 at 3:40

Jason C · Accepted Answer · 2013-11-04 04:10:02Z

2

In theory, a full ternary tree of depth N will have (3^(N+1) - 1) / 2 nodes. If N is 28 that's 34,315,188,682,441 nodes. If each node somehow took only 1 byte that's still 31.2 terabytes of RAM. You'll run out of memory far before then.

Edit: Your code, however, does not appear to generate a full tree. When I ran the following program to count the number of new nodes:

static long nodes = 0;

static void constructTree(int N) {
   if (N > 0) {
       ++nodes;
       constructTree(N-1);
   }
   if (N > 1) {
       ++nodes;
       constructTree(N-2);
   }
   if (N > 2) {
       ++nodes;
       constructTree(N-3);
   }
}

public static final void main (String[] args) throws Exception {
    nodes = 1;
    constructTree(28);
    System.out.println(nodes);
}

Presuming that your TreeNode constructors don't create new nodes, it showed that you are creating 34,850,335 new nodes at N=28, and 64,099,760 new nodes at N=29. This makes more sense given that you implied that N=28 succeeds. Since you don't show your TreeNode we can't tell exactly how much memory it would be using, but these numbers fall within the same order of magnitude as typical JVM memory limits. You could increase your max JVM memory a bit to squeeze one or two more levels out.

However, you may wish to think about precisely why you are generating this tree and try to come up with a different algorithm for doing what you are doing.

edited Nov 4, 2013 at 4:10

answered Nov 4, 2013 at 3:41

Jason C

40.6k16 gold badges136 silver badges201 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Alexander Khaos Greenstein Over a year ago

It was for a homework assignment. Basically it specified that we create the entire tree when the root number was given. I read a comment from one of the TAs that specified "there should be no memory errors." but I think that statement had to do with their test criteria, not our program itself. At the time I didn't realize that, and began to think he meant the program should not have any memory errors. Your descriptions however helped me better understand, as I didn't quite realize my code actually created an unequal tree (although this was what I planned). Thank you so much! And to everyone el

Collectives™ on Stack Overflow

OutOfMemoryError creating a tree recursively?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related