Question :
Suppose a binary tree T has 10 nodes which are labeled 0,1,2,...,9. We ran the inorder and postorder traversals on the tree and the nodes were processed in the following order: inorder traversal: 0,3,1,2,9,4,6,5,8,7 postorder traversal: 0,1,2,3,4,5,6,7,8,9
a. Draw T with its nodes labeled. (Hint: What is the root node? What nodes are in its left subtree? right subtree?)
b. Now consider the general problem. Suppose T is a binary tree whose n nodes are labeled 0,1,...,n-1. You are given two arrays S1 and S2 that correspond to the order in which the nodes were processed in an inorder and postorder traversals respectively.
Design a recursive algorithm that constructs T from S1 and S2. Note that it is enough for your algorithm to describe the children of each node.
What is the running time of your algorithm?