BST Inorder Traversal problem

[Kirby <(^^)>]

Hi guys,

Let me first say that I'm new to this forum, I've read some topic here with great interest but now that I've stumbled on a problem I thought you guys might be able to help me. :)

I've created a program which implements binary trees. I'm required to output the elements of all nodes in a (sub)tree in a natural order. I immediately thought of using Inorder Traversal. The, recursive method I want to use is this:

public static void printInOrder(BSTNode top) {
   if (top != null) {
      printInOrder(top.left);
      System.out.println(top.element);
      printInOrder(top.right)
   }
}

However, the trick is that I don't want to print the values but I want to store them in a string and output them at the end.
Something like this:

public static String printInOrder(BSTNode top) {
?
?
?
   Return aString
}

I can't seem to make a simple recursive method which does this :/
Maybe you guys can help me?

[Eranga]

So keep them in a global position.

[JosAH]

Hi guys,

Let me first say that I'm new to this forum, I've read some topic here with great interest but now that I've stumbled on a problem I thought you guys might be able to help me. :)

I've created a program which implements binary trees. I'm required to output the elements of all nodes in a (sub)tree in a natural order. I immediately thought of using Inorder Traversal. The, recursive method I want to use is this:

public static void printInOrder(BSTNode top) {
   if (top != null) {
      printInOrder(top.left);
      System.out.println(top.element);
      printInOrder(top.right)
   }
}

However, the trick is that I don't want to print the values but I want to store them in a string and output them at the end.
Something like this:

public static String printInOrder(BSTNode top) {
?
?
?
   Return aString
}

I can't seem to make a simple recursive method which does this :/
Maybe you guys can help me?

Pass a second argument to the (recursive) method, say, a StringBuffer and append each data element to it. When your method has finished the Buffer contains all data in inorder traversal; something like this will do it:

public static StriingBuffer printintInOrder(BSTNode top, StringBuffer sb) {
   if (top != null) {
      printInOrder(top.left, sb);
      sb.append(top.element);
      printInOrder(top.right, sb)
   }
   return sb;
}

Note that the method returns the same StringBuffer for convenience.

kind regards,

Jos

[Kirby <(^^)>]

So keep them in a global position.

Yeah that's the easiest solution, but global variables are evil and are not a very elegant solution to a problem.

Pass a second argument to the (recursive) method, say, a StringBuffer and append each data element to it. When your method has finished the Buffer contains all data in inorder traversal; something like this will do it:

public static StriingBuffer printintInOrder(BSTNode top, StringBuffer sb) {
   if (top != null) {
      printInOrder(top.left, sb);
      sb.append(top.element);
      printInOrder(top.right, sb)
   }
   return sb;
}

Note that the method returns the same StringBuffer for convenience.

kind regards,

Jos

Hi Jos, ty for your input.
I also thought about a solution like this however this way the code won't produce the right sequence but will just terminate with the value at the root :(
Let's take this BST for example:

    D
   /\
  B   F
 /\   /\
A C  E  G

I obviously want it to return the sequence A,B,C,D,E,F,G

The way the algorithm works:

inOrderTraversal(D);
   inOrderTraversal(B);
      inOrderTraversal(A);
         inOrderTraversal(NULL);
      print(A)
         inOrderTraversal(NULL);
    print(B)
.
.
.

So if we add a return statement after the if-statement it will just do that after it hits a leaf-node..

I think i might have to rewrite the algorithm for it to work, but since I'm already not that great with visualising recursion that gonna be bothersome..

I had an idea of maybe writing in something similiar to this:

public static String inOrder(BSTNode aNode, String sb) {
        return sb + inOrder(aNode.left, "") + " " + aNode.element.toString() + inOrder(aNode, "");
    }

But I have no idea how to implement the additional conditions (stop if you hit a reference to a null-node) in this kind of form. :(

Maybe you guys can have another look at it, thnx in advance :)

[JosAH]

Maybe you guys can have another look at it, thnx in advance :)

Erm, did you actually have a look at my reply?

kind regards,

Jos

[Kirby <(^^)>]

Erm, did you actually have a look at my reply?

kind regards,

Jos

Yeah I did, I even compiled your suggestion. But after this post I went trough my code again and I realised I made a stupid String/StringBuffer error!
Probably cause I never use stringbuffers, silly me :rolleyes:
Dankjewel! :D

[Eranga]

Yeah that's the easiest solution, but global variables are evil and are not a very elegant solution to a problem.

Of course. I should mentioned with my post.

Easiest way is not the suitable one in most of the cases.