leetExpert
Practice

Construct Binary Tree from Preorder and Inorder Traversal

Module 17 · Binary Trees

Problem

Given two integer arrays preorder and inorder — the preorder and inorder traversal of the same binary tree (all values unique) — reconstruct and return that binary tree. (LeetCode 105.)

Examples

Example 1

Inputpreorder = [3,9,20,15,7], inorder = [9,3,15,20,7]Output[3,9,20,null,null,15,7]
text
      3
     / \
    9  20
       /  \
      15   7

Constraints

1 ≤ n ≤ 3000 nodes · all values unique (load-bearing — see below)

Attempt it first

This problem asks you to reverse two of the DFS Traversals concept lesson's outputs back into the tree that produced them. Before opening anything, work out two facts precisely: (1) given only preorder, which single element do you know for certain is the root, and why? (2) once you know the root's value, what does that tell you about how inorder splits into "everything in the left subtree" and "everything in the right subtree"?