Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Tree Creation Via Traversal Output

  1. Dec 9, 2008 #1
    Hi, I'm familiar with tree traversal alogirthms, post,pre and in-order. If you give me a tree I can print out the specified traversal of that tree. However, one thing I can't do is build a tree from a given output. For example, on my last test, my prof gave me this Question:

    A pre-order of a binary tree produced: ADFGHKLPQRWZ
    A post order traversal of the same tree produced: GFHKDLAWRQPZ
    Draw the binary tree.

    How do you build a tree using two given traversal outputs?
  2. jcsd
  3. Dec 10, 2008 #2
    Hm, I don't know of a specific algorithm or method for doing this but I don't think it should be that hard.

    Just consider what the pre and post order sequences tell you about where nodes are in relation to each other.

    I would suggest starting with the two most obvious pieces of information the pre and post order tell you:

    - The root is A (first letter of preorder)
    - The leftmost node is G (first letter of postorder)

    If it were me I would try drawing those two letters on a piece of paper and then try to fit in the rest of the letters one by one...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook