-
Notifications
You must be signed in to change notification settings - Fork 0
ss18/PTree
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
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
About
Restore a binary tree
Topics
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published