How do I build a binary tree in Java using this method?

Question

I have a recursive Java method that builds a binary tree:

BT build() {
   return(a[++k] == 0 ? null : new BT(build(), build()));
}

BT is a class that looks like this:

class BT {
  BT L; BT R;
  BT(BT l, BT r) { 
      L = l; R = r; 
  }
}

How does the build class work? If I wanted to build a tree with N nodes, then how many times would the build function be called in terms of N?

Also, a and k are never passed as arguments and are not declared. I'm assuming those are class variables you haven't shown? — swinefish
– swinefish, Commented Jan 21, 2016 at 6:54
This very much seems like homework from a college / university course on recursion and code complexity, and some parts of the assignment (a, k) have been left out. — Martin Carpella
– Martin Carpella, Commented Jan 21, 2016 at 7:49

Henry · Accepted Answer · 2016-01-21 08:04:49Z

1

Each call of the build function either creates a node or returns null.

There are always N+1 null pointers in a binary tree with N nodes. This is because each node has 2 outgoing edges and each node, except the root, has one incoming edge.

This gives 2*N+1 calls of build to create a tree with N nodes.

answered Jan 21, 2016 at 8:04

Henry

43.9k7 gold badges75 silver badges89 bronze badges

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

1 Comment

Henry Over a year ago

@33ted since k is incremented exactly once per call of build this should not be too difficult to work out ;-)

Collectives™ on Stack Overflow

How do I build a binary tree in Java using this method?

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