Reconstruct a tree from two traversals

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).

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Reconstruct a Binary Tree from Preorder and Inorder Traversals

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.

Hints

1. The first element of preorder is always the root of the (sub)tree.
2. Find the root's position in inorder: everything to its left is the left subtree, everything to its right is the right subtree.
3. Precompute a value->index hash map of inorder so locating each root is O(1) instead of O(n), giving overall O(n) time.
4. 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.
5. Validate first: if lengths differ or the value sets differ, the input cannot form a valid tree; return the 'INVALID' sentinel.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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).

Recommended Approach

Choose traversal based on the required view or aggregate. DFS is natural for subtree computations and reconstruction; BFS is natural for level order or side views. Keep per-depth or per-position state when the output depends on columns, rows, or depths.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Most tree traversals are O(n) time and O(h) recursion stack for DFS or O(w) queue space for BFS, where h is height and w is maximum width.

Edge Cases and Tests

Empty tree, one node, skewed tree, duplicate values when reconstruction assumes uniqueness, deep recursion, and tie-breaking for same row/column nodes.