Search code examples
posttreebinary-treetree-traversalpreorder

Pre Order, In order, and Post Order Tree Traversals


I am confused about in order, pre-order and post-order traversals, specifically this one, Pre-Order: ABAB, Post Order: BABA, In Order: AABB.

I understand that the root is the first and last element of Pre and Post, but I fail to understand how to finish constructing the Binary Tree.


Solution

  • Your post is vague, and doesn't make much sense, but I'll explain in, pre, post order and constructing a binary tree for you.

    One of the reasons your question doesn't make sense is you haven't established an order to the elements you describe in ordering, ABAB BABA and AABB means absolutely nothing with out a tree to properly show where each element goes (and is each element a letter? why do they duplicate)

    Another reason why your question doesn't make sense is that you appear to think that pre, pos and in order have something to do with creating a binary tree, they don't.

    Pre ordering, In Ordering, and Post Ordering are all types of Depth First Search algorithms for tree traversal. That is to say they are ways of navigating a tree, not creating one. You may use these algorithms to find elements, or to simply print out all the contents of a tree, this is especially useful to a tree who's nodes are only linked via pointers (as apposed to say, an array based binary heap).

    Imagine the following binary tree (the same for all examples)

         A
       B   C
      D E F G
    

    Pre order traversal is a type of tree traversal algorithm where you always take the left most path first. When you can't go farther, you take the next most left path, and do the same thing recursively on the next node. In the above example tree, pre order traversal would start at the root, (A) go left (A,B) go left again (D) couldn't go left so then would go right (E) and in the end you would end up with the following traversal sequence: A B D E C F G

    In order traversal is similar to pre-order traversal, but instead of displaying at each step, in order traversal goes the deepest left it can go, then displays, and if it can't go deep enough any more, it goes back up, displays (hence 'in' order), and tries the same thing to the right again recursively until its done. In the tree example, we'd actually print D first, go back up to B, and print B, then E, then back up to A, and so on, so the final output would be D B E A F G C. Note Wikipedias example may make more sense as it is more complicated.

    In post order, we print from bottom up essentially, we find the deepest node in the left subtree, and print the deepest nodes in there recursively until we're done, go to the right subtree and finally print the root eg: D E B F G C A. Again this example makes more sense with wikipedia, since they have a more complicated tree.

    If you want to construct a tree, there are many ways to do so but it depends entirely what kind of ordering structure you want. Do you want to have a binary structure or n-ary structure? Do you care about which element is on top, or do you only want the min/max (like a pairing heap or binary heap priority queue)? Do you have a search condition, such that the roots of each part of a tree must be larger/smaller/other condition relative to the children or their parents? (like a binary search tree)

    This post is also good explaining the traversals if this isn't sufficient, it also explains why you need different types of ordering in order to construct a tree from a sequence of nodes with proper connections (if your original intent was to copy a binary tree structure)