For a binary tree, one of the traverse result is given as an input, your algorit

Question

For a binary tree, one of the traverse result is given as an input, your algorithm should create corresponding two other traverse results. For example if in-order traverse is given, the pre-order and post-order should be created. a) pseudocode for your method, b) the program with comments, c) Big-O analysis, d) your program's outputs for the following exact three inputs, in the same order: 1) Pre-order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 Post-order: ??? In-order: ??? 2) In-order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 Pre-order: ??? Post-order: ??? 3) Post-order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 Pre-order: ??? In-order: ???

Explanation / Answer

Given any one of the three orders alone, we cannot generate the binary tree [i.e, we cannot generate the other two order]. But however, given "pre-order + in-order" or "post-order+in-order", we can generate the original tree. And moreover, the question says it is a binary tree, not binary search tree or any other specific tree.

To understand this further let's take an example. Consider pre-order : {1,2,3,4,5}
Here we can easily see that '1' is the root of the tree, but can we go more further and say what is the left and right child? No, we can't. There are lot's of possibilities for that. Therefore, we need in-order traversal along with it to know what are left and right subtrees. Let's extend the example and take in-order traversal = {4,5,1,2,3}. Here the left subt-tree has {4,5} and right subtree has {2,3}. Similarly, we can repeat the same steps to deduce the entire tree.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.