Reconstruct a tree from two traversals
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given two arrays representing the preorder and inorder traversals of a binary tree with unique values, reconstruct the tree and return its root. Achieve O(n) time and O(n) extra space. Describe how you would detect and handle invalid inputs that cannot form a valid tree. Write unit tests covering typical, edge, and degenerate cases (e.g., empty tree, single node, skewed trees, mismatched arrays).
Quick Answer: Reconstruct a tree from two traversals evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given two arrays `preorder` and `inorder` representing the preorder and inorder traversals of a binary tree with **unique** values, reconstruct the tree and return it.
Because a tree object cannot be returned directly here, return the reconstructed tree as a **level-order (BFS) list** using `None`/`null` placeholders for missing children, in the same style LeetCode serializes trees (trailing nulls trimmed).
Also handle invalid input that cannot form a valid tree:
- Return `None`/`null` for an empty tree (both arrays empty).
- Return the string `"INVALID"` when the two arrays have different lengths, or when they do not contain the same multiset of values.
Target complexity: **O(n) time** and **O(n) extra space**.
**Examples:**
- `preorder = [3,9,20,15,7]`, `inorder = [9,3,15,20,7]` -> `[3, 9, 20, None, None, 15, 7]`
- `preorder = [-1]`, `inorder = [-1]` -> `[-1]`
- `preorder = []`, `inorder = []` -> `None`
- `preorder = [1,2,3]`, `inorder = [3,2,1]` -> `[1, 2, None, 3]` (left-skewed)
- `preorder = [1,2]`, `inorder = [1,2,3]` -> `"INVALID"` (length mismatch)
Constraints
- All node values are unique.
- 0 <= n <= 10^4 where n = len(preorder) = len(inorder) for a valid tree.
- preorder and inorder must contain the same multiset of values to form a valid tree; otherwise return 'INVALID'.
- If the two arrays differ in length, return 'INVALID'.
- For an empty tree (both arrays empty), return None.
Examples
Input: ([3,9,20,15,7], [9,3,15,20,7])
Expected Output: [3, 9, 20, None, None, 15, 7]
Explanation: Typical balanced-ish tree: root 3 has left child 9 and right child 20; 20's children are 15 and 7.
Input: ([-1], [-1])
Expected Output: [-1]
Explanation: Single-node tree with a negative value — just the root.
Hints
- The first element of preorder is always the root of the (sub)tree.
- Find the root's position in inorder: everything to its left is the left subtree, everything to its right is the right subtree.
- Precompute a value->index hash map of inorder so locating each root is O(1) instead of O(n), giving overall O(n) time.
- Walk preorder with a single shared cursor (left-to-right) while recursing into left then right inorder ranges — this naturally consumes roots in preorder order.
- Validate first: if lengths differ or the value sets differ, the input cannot form a valid tree; return the 'INVALID' sentinel.