I have this thing and I would like people who know a lot about java to try and see who's right.


Ok here's the deal....


I had a test today with the course 'datastructures & algebra' uses java as the main language. This one problem was like this:

You have to write a class in java that should build a binary tree, with each node having 2 children with height n by only using the constructor and no other methods. The tree should have a String variable saying "left" for the left child en "right" for the right node. Also it should have a reference to it's parent. So calling Tree(4) should construct a decission tree with height 4.

Well the only logic way I can think of (the only way they taught us to construct a tree) is using Recursion (letting a method call itself again until the tree is completely constructed).

One of my friends who did the same exam said he asked the teacher and that also the teacher agreed that recursion can't be used with only a constructor, but adding a private method would help a lot.

I didn't use a private method, and I just made a little test program in 2 minutes to see if recursion works.... this is what it looks like:


public class TestRec{

            public int x;
            public TestRec kind;

            public TestRec(int i){
                        if (i != 0){
                                     kind = new TestRec(i - 1);
                                     x = i;
                                     System.out.println(i + "");
                        }
            }
}

public class Test{
            public static void main(String[] args){
                        TestRec test = new TestRec(6);
            }
}

and it produces a column with numbers from 1 to 6..... this is recursion, right? With only a constructor?  

I guess everyone here is java noobs? :P

not a Java n00b at all, but trying to understand what your output is going to look like.  Do you want something like this:

  L----X----R
         |
  L----X----R
         |
  L----X----R
         |
  L----X----R

X being your nodes, L and R being Left and Right.  

K, I deleted a lot of rambling now lol...  I ran your code, and yes it prints out what you need, and it has an archaic way to progress down the tree.  I know there is a reason why i dont like the recursive call to its own constructor, I just dont remember what the pitfall is right now...  Knew I shoulda paid more attention and the JavaOne conference a few months ago lol...  #### them for having Unreal Tournament lan'd there...

The actual problem I had at the exam isn't really something that has to be explained here. It's just the idea of recursion in the constructor, whether it works or not.

Anyway the idea of the tree was kinda like this:

                             Root
                            /      \
                          L         R
                        /   \     /   \
                      L      R  L     R

...etc.

That friend who's being stubborn said there was a problem with using the constructor like that.... I can't think of a problem that could occur though.

Your example doesn't really make the tree...

public class Tree {
  Tree parent, left, right;
  String where;
  public Tree(Tree parent, int level, String where) {
     this.parent = parent;
     this.where = where;
     if(level-- == 0) return;
     left = new Tree(this, level, "L");
     right = new Tree(this, level,"R");
  }
}

public static void main(String args[]) {
Tree tree = new Tree(null, 4, "Root");
}

Now u need a public method to print the tree...

As for recursive constructors... They are bad if u fail to terminate the recursion  

There is also a problem related to Polymorphism, how to pass on the class type you are trying to make a tree of...

I don't know my head from my ass in java but I do know what recursive means, It's a series of numbers where you can not get the next number in the series without the one prior to it.

an = a(n-1) + 3    <--- recursive sequece...I don't know how to do subscripts though n and n-1 should be subscripts

kewl.  And here I was thinking out a dynamic solution when I woke up this AM where you would pass in the dimensions of the tree hehe  was gonna geek out on this at some point, but looks like you have what ya need...

Fuz, I know it doesn't make a tree in my example. That just makes a linear line of objects. As I said it was to test whether recursion works in a constructor, not to test whether my tree works. Besides that for a tree it's not much different except that you need to make another child for each node.

sp00n you're right too. You just create a tree of which Tree(4) creates a tree of 4 levels, and then with recursion you call Tree(4 - 1) and the next one will call Three(4 - 1 - 1) etc which is correct cuz the left node of a tree is also a tree but with one layer less.

About recursive constructors being bad when not ending it, it's also bad when it doesnt end in a void. You'll run out of stack space either way. So that can't be the reason why it shouldn't work.


*edit*

I just thought about something.... maybe it's a bad idea to use recursive constructors because the object you're passing on hasn't been created yet?