Results 1 to 7 of 7
  1. #1
    Kirby <(^^)> is offline Member
    Join Date
    Dec 2010
    Posts
    3
    Rep Power
    0

    Default BST Inorder Traversal problem

    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:

    Java Code:
    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:

    Java Code:
    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?

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,435
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Kirby <(^^)> View Post
    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:

    Java Code:
    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:

    Java Code:
    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:

    Java Code:
    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
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    Kirby <(^^)> is offline Member
    Join Date
    Dec 2010
    Posts
    3
    Rep Power
    0

    Default

    Quote Originally Posted by Eranga View Post
    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.


    Quote Originally Posted by JosAH View Post
    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:

    Java Code:
    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:

    Java Code:
        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:

    Java Code:
    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:

    Java Code:
    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 :)
    Last edited by Kirby <(^^)>; 12-24-2010 at 03:18 PM.

  5. #5
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,435
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Kirby <(^^)> View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    Kirby <(^^)> is offline Member
    Join Date
    Dec 2010
    Posts
    3
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    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

  7. #7
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Quote Originally Posted by Kirby <(^^)> View Post
    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.

Similar Threads

  1. Array traversal issues
    By sondratheloser in forum New To Java
    Replies: 3
    Last Post: 08-13-2012, 12:49 AM
  2. Focus Traversal Demo in SWT
    By Java Tip in forum SWT
    Replies: 0
    Last Post: 07-07-2008, 04:37 PM
  3. Bidirectional Traversal with ListIterator
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-16-2008, 10:37 PM
  4. JTable Focus Traversal
    By helios_lie in forum AWT / Swing
    Replies: 1
    Last Post: 12-20-2007, 10:27 AM
  5. Preorder Traversal problem...
    By tuckker in forum New To Java
    Replies: 3
    Last Post: 12-04-2007, 06:06 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •