1

Two of the exercises for my Data Structures and Algorithms class sound like this

Construct the tree whose preorder traversal is: 1, 2, 5, 3, 6, 10, 7, 11, 12, 4, 8, 9, and inoder traversal is 5, 2, 1, 10, 6, 3, 11, 7, 12, 8, 4, 9.

Construct the tree whose postorder traversal is: 5, 2, 10, 6, 11, 12, 7, 3, 8, 9, 4, 1, and inoder traversal is 5, 2, 1, 10, 6, 3, 11, 7, 12, 8, 4, 9.

I only have to draw the structure of the tree, without implementing it in a programming language. The thing that makes this tasks harder is that the trees are not binary trees. What techniques could I use to build the trees?

Improve this question
7
  • Yes, that would make sense..but this is one of the possible subjects for my midterm. Commented Apr 18, 2013 at 17:37
  • Are you 100% sure they aren't binary trees? If I were you, I would just assume that they are, since this is a requirement for in-order. Commented Apr 18, 2013 at 17:40
  • A few useful notes - the first node is pre-order and the last node in post-order is always the root. The second and second to last nodes are one of the children of the root, you can determine which one by looking at their relation to the root in the in-order traversal. Commented Apr 18, 2013 at 17:42
  • I am sure, this is how the tree should look like: i.imgur.com/RESf0kk.png Commented Apr 18, 2013 at 17:44
  • 1
    @Turdor Ciotlos You can convert the tree in your image to a binary tree that satisfies the conditions. Just move the subtree rooted at 4 to the "right" child of 12. What made you think it couldn't be a binary tree? Commented Apr 18, 2013 at 17:57

1 Answer 1

Reset to default
2

I'm not sure I can give a precise algorithmic solution to this, but I can give a conceptual one that should be sufficient. I think if you could fine-tune it to a well-defined algorithm it would be useful for you and make (that part of) the midterm trivial.

First, think about how an inorder traversal traverses a tree. If you draw the tree so that the leftmost child is to the left (visually) and the other children are to the right (visually) then the inorder traversal loosely goes from left to right. You might run into an issue where it's not quite left to right (because of some overlap between a child of one node and the parent or something like that) but you can always stretch the tree out to make it clearly "left to right". So I take advantage of that by starting my tree with the inorder traversal:

5 2 1 10 6 3 11 7 12 8 4 9

Then the idea is we move nodes up and down according to the preorder traversal. This part is the hard to define part. Basically you move nodes up if they're visited "earlier" and move them down if they're visited later. So, for instance, 1 is to the left of 2 and 5 in the preorder traversal so I raised it "up" in the sense that I made 2 and 5 ancestors (but not necessarily children) of 1. So something like

   1
5 2 10 6 3 11 7 12 8 4 9

Then you see the 2 which comes before the 5, so I raised 2:

    1
  2 
5     10 6 3 11 7 12 8 4 9

Then you see a 3 comes before the 6 and 10 in the preorder traversal so we can "raise" it.

    1
  2        3
5     10 6   11 7 12 8 4 9

And so on. Note that the 3 could eventually be a child of 2 or 1... the tree that satisfies the above constraints isn't unique.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks! What about postorder&inorder? I know the root is the right-most element of the postorder traversal, but what steps should I take to create the tree?
I haven't actually tried it, but I am pretty sure you can just invert the logic and pull it down if it comes earlier in the postorder traversal than it does in the inorder traversal (instead of up).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.