Creating A Binary Tree From Two Traversal Output

Question

This is homework, but for some reason it would not allow me to add the homework tag.

We were assigned a lab for data structures in which the last question asked us to find the binary tree that would produce the following output from the given traversal methods:

LRN: 12, 9, 4, 7, 1, 14, 8, 13, 10, 15, 11, 2, 5, 16, 6, 3

and

LNR: 12, 3, 4, 9, 8, 1, 7, 14, 6, 13, 10, 16, 5, 15, 2, 11

I have identified the following about the tree:

The root node is 3. The root nodes left child and only left child of the tree is 12. The root nodes right child is 6. The furthest right node is 5.

Unfortunately I am stuck as to how to proceed. Any hints would be greatly appreciated.

What types of traversal are showing? preorder and inorder?

lrleon
– lrleon

2015-11-08 02:59:48 +00:00
Commented Nov 8, 2015 at 2:59 — lrleon
– lrleon, Commented Nov 8, 2015 at 2:59

poorvank · Accepted Answer · 2015-11-03 09:05:06Z

4

From the post-order(LRN), we know that last element is the root. We can find the root in in-order(LNR). Then we can identify the left and right sub-trees of the root from in-order.

Using the length of left sub-tree, we can identify left and right sub-trees in post-order array. Recursively, we can build up the tree.

Check this link.

answered Nov 3, 2015 at 9:05

poorvank

7,63221 gold badges65 silver badges102 bronze badges

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

Collectives™ on Stack Overflow

Creating A Binary Tree From Two Traversal Output

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related