Is it possible to rebuild binary tree from its postorder and preorder traversal?
typescript
Ethan JacksonI 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?
Answer
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
