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...
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Tree Creation Traversal Date
C/++/# 3d space filling tree Apr 5, 2017
Minimum Spanning Tree in R Mar 3, 2017
Different Node Deletion/Insertion in a Binary Search Tree Oct 23, 2016
C/++/# Djikstra's algorithm with distance 1 between every node Sep 25, 2016
List file creation date in bash Nov 12, 2012