Suppose a binary tree T has 10 nodes which are labeled 0,1,2,...,9. We ran the inorder and postor...

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?