Construct Binary Tree From Preorder And Inorder Traversal

Medium · Trees

You are given two integer arrays describing the same binary tree: one lists node values in preorder (root, then left subtree, then right subtree) and the other lists them in inorder (left subtree, then root, then right subtree). All values are distinct. Rebuild and return the original binary tree.

Examples

Input:  preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,15,7]
Why:    The first value of preorder, 3, is the root; it splits inorder into left part [9] and right part [15,20,7], which recursively rebuild the original tree.

Input:  preorder = [-1], inorder = [-1]
Output: [-1]
Why:    A single node with no children matches both traversals trivially.

Input:  preorder = [1,2], inorder = [2,1]
Output: [1,2]
Why:    Root is 1 (first in preorder); inorder shows 2 appears before 1, so 2 is the left child.

Constraints

1 <= preorder.length == inorder.length <= 3000, -3000 <= preorder[i], inorder[i] <= 3000, all values in each array are unique, and inorder is a permutation of preorder

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Construct Binary Tree From Preorder And Inorder Traversal

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Construct Binary Tree From Preorder And Inorder Traversal. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.