Rebuild a binary tree from its preorder and inorder traversal arrays.
You are given two integer arrays representing the preorder and inorder traversals of the same binary tree with distinct values.
Reconstruct the original binary tree and return its root.
A preorder traversal visits nodes in the order: root, left subtree, right subtree. An inorder traversal visits nodes in the order: left subtree, root, right subtree.
There is guaranteed to be exactly one valid tree for the given traversals.
Input Format
preorder: an array of distinct integers representing the preorder traversalinorder: an array of distinct integers representing the inorder traversal
Output Format
- Return the root node of the reconstructed binary tree.
Constraints
- The arrays contain the same set of values
- All values are distinct
- The traversals describe exactly one binary tree
- Typical interview constraints: or similar
Example 1
Input
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]
Output
[3,9,20,null,null,15,7]
Explanation
The root is 3. In inorder, values left of 3 belong to the left subtree and values right of 3 belong to the right subtree.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.