Thread: Constructing a binary tree from its in-order and post-order traversals

  1. #1
    Registered User
    Join Date
    Nov 2006
    Location
    Coimbra, Portugal
    Posts
    64

    Constructing a binary tree from its in-order and post-order traversals

    Hi everyone. I'm not gonna lie to you - this is part of an assignment. However, I didn't come here to ask for code.

    You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.

    Input

    The input file will contain a description of the binary tree given as the inorder and postorder traversal sequences of that tree. Your program will read two line (until end of file) from the input file. The first line will contain the sequence of values associated with an inorder traversal of the tree and the second line will contain the sequence of values associated with a postorder traversal of the tree. All values will be different, greater than zero and less than 10000. You may assume that no binary tree will have more than 10000 nodes or less than 1 node.

    Output

    For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you should pick the one with the least value on the terminal node.

    Sample Input

    3 2 1 4 5 7 6
    3 1 2 5 6 7 4
    7 8 11 3 5 16 12 18
    8 3 11 7 16 18 12 5
    255
    255

    Sample Output

    1
    3
    255
    Right, my only question right now is how can I construct a binary tree from its in-order and post-order traversals?

    In-order: 3 2 1 4 5 7 6
    Post-order: 3 1 2 5 6 7 4

    Here's what I know so far in this example: 4 is the root, because it's the last element in the post-order sequence; 3 is the leftmost element, because it's the first element in the pre-order sequence.

    However, I seem to have a hard time sorting out an algorithm to build the rest of the binary tree. Can you please point me in the right direction? Thank you in advance.
    Last edited by CornedBee; 02-15-2008 at 05:33 AM. Reason: Please don't use code blocks for normal text.
    Name: Miguel Martins
    Date of birth: 14th August 1987

    "He who hesitates is lost."

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Well, let's keep working at this example then: 4 is the root. So 3 2 1 are on the left (from inorder); since they appear as 3 1 2 in post order, we know that 2 is the root of this subtree; we know then that 3 is on the left and 1 is on the right (from inorder).
    Simillarly: 5 7 6 are on the right (from inorder); since they appear as 5 6 7 in postorder, 7 is the root of the subtree, so 5 is on the left and 6 is on the right (from inorder).

    In other words: hey recursion!

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    You are on the right track. Using the last entry of the post-order, you can find the root of the tree. In this case, 4. So split the in-order list into two lists on either side of 4: [3 2 1] and [5 7 6].

    You now have two subtrees with a root of 4, and a post-order list of 3 1 2 5 6 7. The post-order list is in two halves (not guaranteed to be equal in size mind you). These halves are just reorderings of the in-order subtrees. Since you have [3 2 1] and [5 7 6] this would imply splitting the post-order sequence into [3 1 2] and [5 6 7].

    So now the original problem is reduced to two smaller problems of the same kind. This is a recursive method.

    EDIT: If the tree is full, and balanced, then you do not need the post-order sequence to reconstruct the tree. See if you can understand why that's true.

  4. #4
    Registered User
    Join Date
    Nov 2006
    Location
    Coimbra, Portugal
    Posts
    64
    Thank you both for your help. I have successfully coded an algorithm to construct those binary trees.

    The output for the second one (in-order: 7 8 11 3 5 16 12 18, post-order: 8 3 11 7 16 18 12 5) is:

    Value: 5
    Right child: 12
    Left child: 7

    Value: 12
    Right child: 18
    Left child: 16

    Value: 18
    Right child: null
    Left child: null

    Value: 16
    Right child: null
    Left child: null

    Value: 7
    Right child: 11
    Left child: null

    Value: 11
    Right child: 3
    Left child: 8

    Value: 3
    Right child: null
    Left child: null

    Value: 8
    Right child: null
    Left child: null

    5 is the root.
    ...which seems to be correct. The output of the first one also seems to be correct, and so is the third one's output.

    Finding the solution to the assignment should be piece of cake now. Thank you once again.
    Name: Miguel Martins
    Date of birth: 14th August 1987

    "He who hesitates is lost."

  5. #5
    Registered User
    Join Date
    Mar 2008
    Posts
    1

    another way

    i could be wrong here, as i have not read this elsewhere, but this is an observation of mine.
    an in-order representation of the tree flat out tells you the comparative relationship between each element, even if the tree wasn't constructed using some comparative function (such as a "question" tree or an "animal" tree), in which case an in-order traversal still imposes an order to the elements.
    Using this observation, if you know the pre-order or post-order, you know which element the root is. With either representation, if you start inserting each element in the representation, starting at the root and working towards the other end, you can use the infix representation as your comparative function to reconstruct a tree identical to the original. i.e.:

    for some arbitrary tree:

    pre-order representation:
    A B F Q N S W G K L M Z (these are not letters, but some things to which we don't know the
    order, for example, A is not necessarily less then B)

    in-order representation:
    F S N Q W B A K M L Z G

    now, we do not know how the elements where placed in the tree, but for the purposes of reconstruction, using the in-order representation, we can assume that :

    F < S < N < Q < W < B < A < K < M < L < Z < G

    we also know the root is A, so starting from the root and working towards the end of the list, we began inserting using the order imposed by the in-order representation. As an example, using pre-order, we know the root is A, so insert it. The next element B, according to the in-order, is less then A, so B becomes the left child of A. you continue this until you run out of elements. This works
    for post-order as well, you simply work from the end of the list to the front in this case.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 01-09-2009, 12:17 PM
  2. Tree [Level Order Treversal]
    By cfrost in forum C++ Programming
    Replies: 3
    Last Post: 10-21-2004, 12:47 AM
  3. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 06:19 AM
  4. post order iterative help
    By curlious in forum C++ Programming
    Replies: 8
    Last Post: 01-03-2004, 11:43 AM