Interview Question Software Engineer / Developers
No.
However, we can construct a unique Binary Tree using:
1. Inorder & Preorder traversals.
2. Inorder & Postorder traversals.
Guest123,
You didn't read the problem statement correctly. It's a Binary Search Tree (BST) not just a Binary Tree (BT). If it is a BST then you can reconstruct the unique BST with just the preorder traversal.
You are correct for a BT, with one caveat. The nodes need to be uniquely labeled, so you can't have any duplicate labels. If you have duplicate labels, you can't reconstruct the unique BT with any combination of preorder, inorder or postorder traversals.
It's possible to reconstruct the BT when it has duplicate labels, but you need additional data in order to be able to discriminate the duplicate labels correctly.
In fact I was right, preorder (and postorder) traversal outputs are sufficient for unique BST construction . In case of BST inorder output in anyway redundant. its normal binary tree for which we need inorder traversal output along with pre/post order
No you were wrong.
1
/
2
and
1
\
2
have same pre and post order.
SEe this: w w w. cmi. ac. in/ ~ madhavan/ courses/ programming06/ lecture12-21sep2006.txt
It looks like you didn't acknowledge the problem statement correctly. The problem statement says it is a BST, not a binary tree. In fact the sample you give is incorrect with this constraint because the first tree is not a BST.
ABG is correct, you can rebuild a BST with just a preorder or postorder traversal, assuming the ordering is implicit in the traversal,i.e., integers or characters. Plus you use a consistent rule for duplicates, if they are allowed.
This is duplicate question, was seen sooooooo many times in amazon/MS question. What's wrong with this guy?
People should refrain from replying to posts that look like spamming or HOMEWORK!
Preorder traversal is sufficient to construct a BST.
- Kishore Jinka August 30, 2011Preorder + Inorder or Postorder + Inorder or Levelorder + Inorder are required for constructing a BT. Inorder is a must for constructing a BT. However in case of BST you can get the inorder sequence by arranging the numbers in increasing order. So given an Preorder traversal, you can sort them to get Inorder traversal. With the combination of these traversals you can construct your tree.
Google's Question: Write code to construct binary tree using Levelorder and Inorder.