If we have a preorder and postorder traversals of a full binary tree T(i.e every internal node have exactly 2 children). can we uniquely construct the corresponding full binary tree T.If so.. could you give a rough sketch of proof otherwise could you give a counter example
unique binary tree from preorder and postorder traversals of a full binary tree
co.combinatorics;ds.data structures;tree
Well, here's the algorithm:Consider the postorder traversal and replace each node with its index in the preorder traversal.For example, let's say you get: 3 4 2 7 8 6 9 5 1.From here you can see:1 is the root because it's the last node in postorderIt only remains to split 3 4 2 7 8 6 9 5 (without the 1) into two parts: left and right subtree, and then recursively process them.Consider the second problem.Note that this set is of the form: (all nodes of left subtree in some order) (all nodes of right subtree in some order) - i.e. the subtree ranges don't intersect. So we only have to find the boundary, which, given it's postorder traversal, should be the root of the left subtree (it's the last thing processed from the left subtree; all that follows is the right subtree).But note that the root of the left subtree is the item with the smallest preorder index.So this means that in 3 4 2 7 8 6 9 5, the left subtree is rooted at 2, and the problem splits into 3 4 2 and 7 8 6 9 5.Recursively, we get a tree: 1 { left = 2 { left = 3, right = 4}, right = 5 {left = 6 {left = 7, right = 8}, right = 9}}.P.S. Note that in this form the algorithm is O(n log n), but it's easy to make it O(n) - just remember in a lookup table (obviously in O(n)) for each element x of the array, the position of x+1 - then, whenever you pick x as a root, the left subtree ends at the position of x+1.