Requirements needed to construct a unique BT
MediumInorder plus one other order
Problem
Understand which traversal pairs uniquely reconstruct a binary tree (inorder + preorder/postorder yes; preorder + postorder not always).
Inorder tells left-vs-right; pair it with pre or post to pin down the shape.
The idea
Inorder tells you what is left and right of a node but not which node is the root; preorder or postorder supplies the root. Either pair reconstructs the tree uniquely, while preorder plus postorder alone does not.
The trick
- Inorder + preorder, or inorder + postorder: unique.
- Preorder + postorder is ambiguous for nodes with a single child.
- Values must be distinct for any of this to work.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — preorder + inorder Values: 0.
1inorder splits into left/right subtrees2preorder/postorder gives the root to split onInput
- array
- [0]
Output
- answer
- —
Check yourself
2 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- preorder + inorder
- Output:
- unique tree
Finished the walkthrough? Add it to your streak.