## Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
1
of 1 vote

Preorder traversal is sufficient to construct a BST.
Preorder + 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

No.
However, we can construct a unique Binary Tree using:
1. Inorder & Preorder traversals.
2. Inorder & Postorder traversals.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I dont disagree , but I am not able to prove the "need" of inorder.
I have made an algo which is able to build a unique BST using preorder and postorder sequence. Can you please give an example to prove me wrong ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Right. It is BST not BT.

Comment hidden because of low score. Click to expand.
0
of 0 vote

To convert a preorder traversal to BST, following are the conditions:
1.First element will be root.
2.LeftChild=nearest element less than root
3. RightChild=nearest element greater than root

Comment hidden because of low score. Click to expand.
0
of 0 vote

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!

Comment hidden because of low score. Click to expand.
0

visit the nodes and put them in the tree..thats it!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

With only Preorder, one can derive an algo to construct BST.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.