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 binary tree from traversals

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Coding: Build a Binary Tree from Two Traversals You are given two integer arrays representing traversals of the **same** binary tree: - `preorder`: node order is **root → left → right** - `inorder`: node order is **left → root → right** All values are **unique**. ### Task Reconstruct the binary tree and return its root node. ### Input - `preorder`: length `n` (1 ≤ n ≤ 10^5) - `inorder`: length `n` - Values are unique integers. ### Output - Return the root of the reconstructed binary tree (using a standard `TreeNode { val, left, right }` structure). ### Example - `preorder = [3, 9, 20, 15, 7]` - `inorder = [9, 3, 15, 20, 7]` The reconstructed tree is: - root = 3 - left child = 9 - right subtree rooted at 20 with children 15 and 7 ### Notes - Assume the input is valid (both traversals come from one binary tree). - Your solution should be efficient for large `n`.

Quick Answer: This question evaluates understanding of binary tree traversal properties, data structure manipulation, and algorithmic complexity involved in reconstructing a tree from preorder and inorder sequences.

You are given two integer arrays representing traversals of the **same** binary tree with **unique** values: - `preorder`: node order is **root → left → right** - `inorder`: node order is **left → root → right** Reconstruct the binary tree and return it. ### Return format Since a raw tree node is hard to compare directly, return the reconstructed tree as a **level-order (BFS) array** using the standard LeetCode serialization: list node values level by level, using `null` (Python `None`) for a missing child, and trim trailing `null`s. For an empty input, return an empty array. ### Example - `preorder = [3, 9, 20, 15, 7]` - `inorder = [9, 3, 15, 20, 7]` - Returns `[3, 9, 20, null, null, 15, 7]` The tree: root `3`, left child `9` (a leaf), right subtree rooted at `20` with children `15` and `7`. ### Constraints - `1 ≤ n ≤ 10^5` (and an empty array is allowed as a degenerate case) - All values are unique integers - The input is guaranteed to be a valid pair of traversals of one binary tree Aim for an O(n) solution.

Constraints

1 ≤ n ≤ 10^5 (an empty array is also accepted as a degenerate case)
All node values are unique integers
preorder and inorder are valid traversals of the same binary tree
Return a level-order (BFS) array with null for missing children, trailing nulls trimmed

Examples

Input: ([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])

Expected Output: [3, 9, 20, None, None, 15, 7]

Explanation: Root 3; left child 9 is a leaf; right subtree rooted at 20 has children 15 and 7 — the worked example from the prompt.

Input: ([1], [1])

Expected Output: [1]

Explanation: A single node is its own root with no children.

Input: ([], [])

Expected Output: []

Explanation: Empty traversals produce an empty tree.

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

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

Explanation: Left-leaning spine: 1's left child is 2, whose left child is 3; no right children anywhere.

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

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

Explanation: Right-leaning spine: 1's right child is 2, whose right child is 3; null marks each missing left child.

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

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

Explanation: Negative values; root -1 with left child -2 and right child -3, a complete two-level tree.

Input: ([5, 3, 2, 4, 8, 7, 9], [2, 3, 4, 5, 7, 8, 9])

Expected Output: [5, 3, 8, 2, 4, 7, 9]

Explanation: A balanced 7-node tree: root 5, left subtree (3 with 2 and 4), right subtree (8 with 7 and 9).

Hints

The first element of preorder is always the root of the current (sub)tree.
Find the root's position in inorder: everything to its left forms the left subtree, everything to its right forms the right subtree.
Build a value -> index map over inorder once so each root lookup is O(1) instead of a linear scan.
Consume the preorder array with a single moving pointer (or iterator) as you recurse root → left → right; you never need to re-scan it.
After building the tree, run a BFS to serialize it into the level-order array, appending null for absent children and trimming trailing nulls.

Quick Overview

This question evaluates understanding of binary tree traversal properties, data structure manipulation, and algorithmic complexity involved in reconstructing a tree from preorder and inorder sequences.