Ocaml help tree traversal

Question

Problem Description:

Professor R. Borist studies trees. He has kept a record of the preorder, inorder, and postorder traversals of all of his favorite trees. However, a fire in his office has destroyed the file cabinet where he stored the inorder traversals. He still has the preorder and postorder traversals of all of his favorite trees, is this enough information to reconstruct the missing inorder traversals?

You must design and implement a program for the following task: The input will consist of two lists of numbers. The first list is the preorder traversal of some tree T. The second list is the postorder traversal of the same tree T. The output should be the inorder traversal of T. If the input does not determine a unique tree, then any consistent inorder traversal can be returned.

If it helps in designing your implementation, you can assume that:

No tree has more than 1,000 nodes.
No tree uses the same label for multiple nodes.
Labels of nodes are numbers from 0 to 10,000.

Sample data

Input:
2 6 7 1 11 8 5 10 3 4 9
7 8 5 11 10 1 6 4 9 3 2
Output:
7 6 8 11 5 1 10 2 4 3 9

Hints

Given the preorder & postorder traversals of a tree, can you deduce which element was the root? which elements must have come from the left subtree? from the right subtree? Recurse.

First solve the problem when every node in the tree is guaranteed to have either 2 or 0 children. The case in which some nodes have only 1 child is a little trickier.

Notes

In your writeup, you do not need to analyze the efficiency / running time of your solution (this will be a requirement in future projects). But do analyze its correctness; i.e., explain clearly why your algorithm is correct.

This seems more like a logic puzzle than an OCaml problem. The key is that nodes are uniquely numbered. The hint seems pretty good: the root of a left subtree of a node is fairly obvious from preorder. The root of a right subtree of a node is fairly obvious from post order. But what does it mean if these turn out to be the same node? You can continue this recursively to get the whole tree (seems like--I haven't actually solved it!). — Jeffrey Scofield

jrouquie jrouquie · Accepted Answer · 2012-08-15T22:04:52

Even if the problem description does not explicitely says so, it is clear from the hints that we are dealing with binary trees.

The hint is good: find the root of the tree, then find the root of the left subtree and the root of the right one.

After removing the root, look for a position in the list of nodes where you can cut the list: the nodes before the cut are from the left subtree, the nodes after the cut are from the right subtree.

Working out small examples like you did is a good idea.

To answer specifically "understanding how I can build the inorder traversal from the pre and post": first rebuild the tree from the pre and post traversals, then build the inorder traversal from the tree.

Ocaml help tree traversal

1 Answers