Construct Binary Tree from Preorder and Inorder Traversal — Medium Coding Interview Question

Given two integer arrays preorder and inorder representing the preorder and inorder traversal of a binary tree, construct and return the binary tree, returned here as its level-order array.

Example

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

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

Constraints

• 1 ≤ preorder.length ≤ 3000
• inorder.length == preorder.length
• Both arrays consist of unique values

Topics & Companies

Topics: trees

Asked by: Amazon, Microsoft, Meta, Bloomberg

Optimal Solution Complexity

Time complexity: O(n). Space complexity: O(n).

Practice more

• All DSA Problems
• DSA Patterns