Search code examples
javabinary-search-treeinorder

Returning a tree as a string in InOrder sequence

I must write a function which takes in an tree as an argument and returns it as a string in inorder sequence.

This is what I got. 

public static String concatInOrder( StringTreeNode t )
    {

        if(t == null) return "";

        return (t.left+t.val+t.right); 
    }

However I've ran into several difficulties with this. Several questions.

  1. Am I approaching the problem wrongly?
  2. How may I improve my prowess when it comes to Binary Search tree manipulation WITHOUT the use of libraries and such?
  3. What Am I missing? Isn't it true that inOrder sequence is left, current, right? (val is short for value, so the leaf it's currently on.
Solution

  • Yes that's the correct order. The inorder tag you added says that much.

    You need to recursively call the concatInOrder method:

    public static String concatInOrder(StringTreeNode t)
{
    if (t == null) return "";

    return concatInOrder(t.left) + t.val + concatInOrder(t.right);
}