DSA interview question

Which Traversal Pairs Determine a Unique Binary Tree?

Medium · Data structures · Topics: tree, theory

The problem

A backup tool stores binary trees (with distinct values) as two traversal sequences instead of pointers, and the team must pick which two traversals to store so that the tree can always be rebuilt unambiguously. Given two traversal types, coded 1 = preorder, 2 = inorder and 3 = postorder, return whether they always determine a unique tree. The rule is short: the pair must include inorder and one other traversal. Preorder or postorder identify the root; inorder then splits everything else into left and right. Preorder with postorder can't tell a lone left child from a lone right child.

Example: (1, 2) → true; (1, 3) → false.

Function signature

bool isPossible(int a, int b);  // 1 = preorder, 2 = inorder, 3 = postorder

Test cases

Input `(a, b)`	Output	Explanation
`(1, 2)`	`true`	Preorder + inorder
`(2, 3)`	`true`	Inorder + postorder
`(1, 3)`	`false`	"1 with left child 2" and "1 with right child 2" give the same sequences
`(2, 2)`	`false`	Inorder alone doesn't fix the shape
`(3, 1)`	`false`	Order of the arguments doesn't matter

(Confirm: node values are distinct; "unique" means for every tree, not just some trees.)

How interviewers phrase it

"Given two traversals among preorder, inorder and postorder, can they construct a unique binary tree?" (GeeksforGeeks "Unique Binary Tree Requirements").

Clarifying questions to ask

Are the values distinct? (Yes. With duplicates, even pre + in can be ambiguous.)
Are the two traversals of the same tree? (Yes.)
Is a level-order traversal also allowed? (Not in this version; level order + inorder is also enough.)

Follow-ups to expect

"Why does inorder matter?"
"Why can't pre + post do it?"
"How do you actually build from pre + in?"
"And with post + in?"
"Complexity of building?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview