Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.

Problem statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

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 <= 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.

Topics and companies

Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree.

Reported in interviews at Amazon, Microsoft, Facebook, ByteDance, Citadel, Bloomberg, Oracle.

How to practise Construct Binary Tree from Preorder and Inorder Traversal on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N), where N is the number of nodes. Each node is visited once, and all lookups in the hash map are O(1). time and O(N), for the hash map and the recursion stack (in the worst case of a skewed tree). The output vector also takes O(N) space. space.

Open Construct Binary Tree from Preorder and Inorder Traversal in the code editor, or read the Construct Binary Tree from Preorder and Inorder Traversal editorial for a worked solution with its approach and complexity analysis.

Where Construct Binary Tree from Preorder and Inorder Traversal sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Recursive Preorder Traversal subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Construct Binary Tree from Preorder and Inorder Traversal

Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• Binary Tree Paths — Easy, same subpattern
• Flatten Binary Tree to Linked List — Medium, same subpattern
• Invert Binary Tree — Easy, same subpattern
• Same Tree — Easy, same subpattern
• Smallest String Starting From Leaf — Medium, same subpattern
• Symmetric Tree — Easy, same subpattern