Easy Questions

1. What do you obtain when doing an inorder, preorder, and postorder traversal of an expression tree?
2. How can you represent a binary tree in an array? For this, you should map each node in the binary tree to a unique position in the array. What is the (maximum) size of the array required to store a binary tree of n nodes.

Difficult Questions

1. Given an inorder traversal sequence, how many different trees can you draw that have the same inorder traversal?
2. Answer the above question for preorder traversal, and separately for the postorder traversal.
3. How does your answer to the above question change if you are given both the inorder traversal and the preorder traversal? How many trees exist that has the given inorder traversal sequence and the given preorder traversal sequence.
4. Based on your answer to the previous question, write a program that takes as input an inorder traversal sequence and a preorder traversal sequence, and outputs a binary tree that has the given inorder and preorder traversal.