How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Reconstruct a tree from two traversals

Quick Overview

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.

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.

Input: ([], [])

Expected Output: None

Explanation: Empty tree: both traversals are empty, so there is no root.

Input: ([1,2,3], [3,2,1])

Expected Output: [1, 2, None, 3]

Explanation: Left-skewed (degenerate) tree: 1's left is 2, 2's left is 3; no right children.

Input: ([1,2,3], [1,2,3])

Expected Output: [1, None, 2, None, 3]

Explanation: Right-skewed (degenerate) tree: each node has only a right child.

Input: ([1,2], [1,2,3])

Expected Output: INVALID

Explanation: Mismatched array lengths cannot form a valid tree — return the INVALID sentinel.

Input: ([1,2,3], [4,5,6])

Expected Output: INVALID

Explanation: Same length but disjoint value sets cannot correspond to traversals of one tree — return INVALID.

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.

Quick Overview