Two traversal techniques are given by their codes: 1 = preorder, 2 = inorder, 3 = postorder. Given two codes a and b, return true if a unique binary tree can be constructed from those two traversals, and false otherwise.
Input: a = 1, b = 2 Output: true Preorder + inorder determine a unique tree.
Input: a = 1, b = 3 Output: false Preorder + postorder do not determine a unique tree.
- 1 <= a, b <= 3 - a and b are traversal codes (1=preorder, 2=inorder, 3=postorder)
A single traversal never pins down a unique tree, and neither does just any pair. The rule is sharp: two traversals determine a unique binary tree if and only if one of them is the inorder traversal.
“What do 1, 2, 3 mean?”
1 = preorder, 2 = inorder, 3 = postorder.
“Why does inorder matter so much?”
Only inorder tells you which nodes are in the left subtree vs the right.
Preorder or postorder gives me the root, but only inorder tells me where the left subtree ends and the right begins.
So two traversals yield a unique tree exactly when one of them is inorder — I just check if a or b equals 2.
Worked examples
a=1 (preorder), b=2 (inorder) -> inorder present -> unique -> true a=1 (preorder), b=3 (postorder) -> no inorder -> not unique -> false a=2 (inorder), b=3 (postorder) -> inorder present -> unique -> true
Preorder/postorder reveal the root; inorder reveals the left/right split. You need both pieces.
Only inorder locates the boundary between subtrees, so one traversal must be inorder.
Without inorder you can't always tell where the left subtree ends (e.g. a node with a single child).
Key takeaway
Two traversals build a unique binary tree iff one of them is inorder. Return a == 2 || b == 2. O(1).
