algorithmbinary-tree

Is it possible to rebuild binary tree from its postorder and preorder traversal?

I understand we can rebuild a binary tree from its inorder AND ( postorder OR preorder ) traversal.

I however wonder whether rebuilding it from its postorder AND preorder traversal doable too?

Solution

  • Short answer is NO, unless it is also a full binary tree.

    The reason is without inorder traversal you won't be able to resolve the ambiguity of left/right, for instance, the two binary trees below give you the same pre/postorder traversal:

      1                   1
 / \                 / \
2   5       vs      2   5
\   /              /   /
 3 6              3   6