You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:
A distributed system processes hierarchical data such as:
- JSON/XML structures
- execution trees
- dependency graphs
To optimize storage and transmission, the system serializes tree structures into traversal sequences. Two commonly used formats are:
- Preorder Traversal (Root → Left → Right)
- Inorder Traversal (Left → Root → Right)
Your task is part of a reconstruction pipeline where the system receives these two sequences and must rebuild the original tree structure.
This is essential for:
- reconstructing execution flows
- restoring data hierarchies
- debugging distributed systems
The system guarantees that:
- all node values are unique
- the tree can be reconstructed uniquely
This is a classic coding interview problem frequently asked in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given two integer arrays:
Construct and return the binary tree.
Input Format
preorder: array of integersinorder: array of integers
Output Format
- Return the root node of the constructed binary tree
Examples
Example 1:
Input: preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Output: 3
/ \
9 20
/ \
15 7
Example 2:
Input: preorder = [1]
inorder = [1]
Output: 1