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

Trees as Data Structures

  1. Aug 5, 2014 #1


    User Avatar
    Gold Member


    There are three different orders of traversal that we learned about
    ##\bullet## pre-order traversal
    ##\bullet## in-order traversal
    ##\bullet## post-order traversal

    Anyone know of any easy ways of remembering these 3 and how to order them? I have posted my lecture slides, but I could imagine the tree looking differently and then not knowing how to adapt and analyze how the calls would be made to a different looking tree.

    Also, when one writes a recursive program, which order of traversal is taken? Is there some sort of default? Why are there 3 ways of traversing?

    Attached Files:

    Last edited: Aug 5, 2014
  2. jcsd
  3. Aug 5, 2014 #2
    If you write a recursive function (R) to print (P) each node on the tree, you have these choices:
    R(this) { if(this) {P(this); R(this->left); R(this-right) } }
    R(this) { if(this) {R(this->left); P(this); R(this-right) } }
    R(this) { if(this) {R(this->left); R(this-right); P(this) } }

    Note how each yields a different print order.
  4. Aug 5, 2014 #3


    User Avatar

    Staff: Mentor

    There's no default. It's up to you to decide how you want to traverse a binary tree.

    There are actually more than three ways. Consider your "ingredients:"

    • A. Process the data in the node that you're pointing to.
    • B. Process the subtree that the node's left link points to.
    • C. Process the subtree that the node's right link points to.

    How many different sequences can we perform these three items in?

    A, B, C
    A, C, B
    B, A, C
    [you fill in the rest]

    The proper sequence to use depends on what you want to do, that is, what overall algorithm the traversal is part of.
  5. Aug 6, 2014 #4


    User Avatar
    Gold Member

    Okay, well I wrote a recursive function to find the fibonacci number of the ##n^{th}## term in the sequence as the input to the function with the formula for the fibonacci number given as

    ##F_{n} = F_{n-1} + F_{n-2}## with the base case ##F_{1} = 1## and ##F_{2} = 1##

    Code (Text):
    function fibonacci_number = fibnum(n)
    if n < 1
    elseif n == 1 || n == 2
        fibonacci_number = 1;
        fibonacci_number = fibnum(n-1) + fibnum(n-2);
    How do I decipher this to determine the order of traversal taken, or even how this recursive tree will appear? I turned on the breakpoint and am trying to follow it step by step, but it just isn't making sense to me. This could be in part due to an incomplete understanding of how the green and white arrows are interacting, and how the green arrow pointing down means.

    What if I flipped my sum to be fibnum(n-2) + fibnum(n-1)?? Is the first term of the summation the left child of the root node? And it's sibling the right side.

    EDIT: Just discovered that it matters very much indeed. I had it the other way around, so it wasn't calling in the order that my lecture slides indicated, because they had the sum flipped around. Very interesting...But can I manipulate this code to follow a post-order or in-order.

    I did the breakpoint and ran the code step by step, and I see how it is recursively calling, however, I don't see how it is returning the calls.

    Here is the updated code
    Code (Text):
    function fibonacci_number = fibnum(n)
    if n > 2
        fibonacci_number = fibnum(n-2) + fibnum(n-1);
        fibonacci_number = 1;
    Last edited: Aug 6, 2014
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook