ss18 / ptree Goto Github PK

PROBLEM DESCRIPTION:
Restore a binary tree of N nodes, every node is uniquely labeled with a number from 1 to N, given the tree vectors corresponding of the Inorder, Postorder and Preorder iterations of the tree (http://en.wikipedia.org/wiki/Tree_traversal). However, the iterators produce an imperfect result: sometimes, with an unknown uniform probability P, the iterator swaps two connected nodes before iterating them (you can imagine there is a machine reading the data, but the process of reading is stochastic). Every iterator runs on the tree master copy, this means, the changes of one iteration don't affect the others.

To solve the problem, return the true Inorder and Preorder. Optionally, for each element, return the probability of being located in that position by chance (also known as p-value) and approximate P. 

Sample:
Given the "true" tree:

      1

    /  \

   2    3


The true iteration vectors are:
Inorder 2 1 3
Preorder 1 2 3
Postorder 2 3 1

However, your input may look like:

Inorder 2 1 3
Preorder 3 2 1
Postorder 2 3 1

In the case above, the Preorder traversal has mistakenly switched 3 and 1 nodes.
The solution looks like:

Inorder 2 1 3
Preorder 1 2 3

p-values (each value corresponds to the preorder nodes) 1/6  1/216 1/6 posterior probability  P= 1/6