[Help] Recursive method

[ling qin]

hi, i'm writing a recursive method that returns a string containing a binary tree "printed" sideways,with the right subtree above the root node and the left subtree below the root node. Each subtree is indented by three spaces more than its root.

for example, the input binary tree is:

A
/ \
B C
/ \
D E

the returned string shoud be(note the child nodes have 5 spaces idented away from the root):

------D
---B
------E
A
---C

(note that "-" means a space)

This is the method I wrote, the order of the string is correct but the spaces idented is messed up

public String printTree(BinaryTree b) {
if(b.isEmpty)
{ return "";
}else if(b.leftSubtree().isEmpty()&&b.rightSubtree().isEmpty())
{return (String)b.getRoot()+"\n";
}else
{return " "+printTree(b.leftSubtree())+b.getRoot()+" "
+printTree(b.rightSubtree());
}
}

for that input binary tree, the result is like this, which is wrong:

------D
B
---E
A
---C


how can i solve this?thanks
[ November 20, 2006: Message edited by: ling qin ]

[Stan James]

Hey, welcome to the ranch!

I've done lots of these passing the current indent depth or the indent blanks themselves as a parameter. I think you can make it this simple:

print( root, "" )
...
private void print(Node n, String indent )
{
   if node is null, return
   print ( n.left, indent + "---" )
   System.out.println( indent + n.text )
   print ( n.right, indent + "---" )
}

See if that works for you.
[ November 20, 2006: Message edited by: Stan James ]

[ling qin]

Hi Stan,

I'm a bit confused with your code,can you write it again to include more details?
why do you put print(root, "") at the first place?
where is the if statement opend and closed?

the method should return a String, not printout
thanks a lot!!

[ November 20, 2006: Message edited by: ling qin ]
[ November 20, 2006: Message edited by: ling qin ]

[Stan James]

The print(root,"") is outside the recursive method, the initial call that starts everything going.

Building up a string of the whole thing is only slightly trickier. It has the risk that a tree with millions of nodes will run out of memory but not on a small exercise.

private String print(Node n, String indent )
{
   if node is null
      return ""
   return print( n.left, indent + "   " )
        + indent + n.text + "\n" 
        + print( n.right, indent + "   " )
}

Draw your tree on paper and "play computer" to see if this walks through the nodes in the order you want and builds a tree-like picture. Then fix it up a bit to be compilable Java and see what it makes.