Amazon Interview Question
Country: United States
1. Suppose if u persist preorder only postorder than how would u identify that which element will come to the left or which element will come to the right.
2. this will lead us to the different BST from the one which we persisted.
3.So by using only one traversal we will get differnet BSTs with same elements.
As alex said a BST can be reconstructed from the preorder traversal alone.
- lakshaman January 22, 2014It appears the question should actually have been for a binary tree. For binary trees none of three traversals inorder, preorder or postorder alone can uniquely identify the tree. For a binary tree inorder traversal and either a postorder or preorder traversal can uniquely identify the tree.
Importance/Requirement of Inorder traversal:
The inorder sequence will resolve the left-right problem, and the other sequence (pre or post) will tell us the roots of the various subtrees. For example, if inorder is CBA, and preorder is CAB, then we know that C is at the root, and both B and A are in the right subtree