Depth-First Search/Construct Binary Tree from Preorder and Inorder TraversalMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Construct Binary Tree from Preorder and Inorder Traversal

Depth-First Search·Medium

Given two integer arrays preorder and inorder where:

preorder is the preorder traversal of a binary tree,
inorder is the inorder traversal of the same tree,

reconstruct and return the binary tree.

Output convention. Return the tree as a level-order array with null for missing children (LeetCode serialization), with trailing nulls trimmed.

Examples

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

Input: preorder = [-1], inorder = [-1]

Output: [-1]

Constraints

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values.
Each value of inorder also appears in preorder.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Depth-First Search
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.