Tree Creation Via Traversal Output

  • Thread starter Ecurb
  • Start date
1
0
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?
 
558
1
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...
 

Related Threads for: Tree Creation Via Traversal Output

  • Posted
Replies
5
Views
2K
Replies
9
Views
717
  • Posted
Replies
5
Views
7K
  • Posted
Replies
1
Views
4K
  • Posted
Replies
2
Views
2K
  • Posted
Replies
9
Views
841
  • Posted
Replies
3
Views
3K
  • Posted
Replies
11
Views
3K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top