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.
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.