Build a Binary Tree from Preorder and Inorder
Problem statement
Given two integer arrays $\mathrm{preorder}$ and $\mathrm{inorder}$ representing the preorder and inorder traversals of a binary tree with distinct values, construct the tree and return its root.
Constraints:
- $1 \le n \le 3000$, where $n = \mathrm{len}(\mathrm{preorder}) = \mathrm{len}(\mathrm{inorder})$
- All values are distinct, and $\mathrm{inorder}$ is a permutation of $\mathrm{preorder}$.
Examples:
- $\mathrm{preorder} = [3,9,20,15,7]$, $\mathrm{inorder} = [9,3,15,20,7] \to$ root $3$, left child $9$, right subtree rooted at $20$ with children $15$ and $7$.
- $\mathrm{preorder} = [-1]$, $\mathrm{inorder} = [-1] \to$ a single node $-1$.
Show hint
What does each traversal order tell you about where a subtree's root sits relative to its descendants?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.