Blind 75 / Trees / Construct Binary Tree From Preorder And Inorder Traversal

Construct Binary Tree From Preorder And Inorder Traversal

MediumTrees
Asked byMicrosoftBloombergGoogleAmazonUberByteDance

Problem

Given two integer arrays representing the preorder and inorder traversal of a binary tree with unique values, construct and return the binary tree.

Examples

Example 1
Input:preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output:[3,9,20,null,null,15,7]
Example 2
Input:preorder = [-1], inorder = [-1]
Output:[-1]

Constraints

  • 1 <= number of nodes <= 3000, and all values are unique.

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Trees pattern

A tree is a hierarchical structure where each node has at most a fixed number of children (two, for binary trees). Almost every tree problem reduces to a traversal — decide what order you visit nodes in, and what you do at each one.

Look for this pattern when

  • The problem is naturally recursive: "the answer for this tree depends on the answer for its subtrees."
  • You need level-by-level information (BFS) versus depth-first structural information (DFS).

Read the full Trees guide →

Video walkthroughs

Original problem on LeetCode ↗

More Trees problems

← Kth Smallest Element In a BstBinary Tree Maximum Path Sum →