TIC
The Interns Company

Construct Binary Tree from Preorder and Inorder Traversal

MediumAcceptance: 58.2%
ArrayHash TableDivide and ConquerTreeBinary Tree

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.

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

Input Format:

  • Two integer arrays preorder and inorder

Output Format:

  • Return the root of the constructed 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]

Explanation:

This creates a binary tree with root value 3, left child 9, and right child 20. Node 20 has left child 15 and right child 7.

Example 2:

Input:

preorder = [-1], inorder = [-1]

Output:

[-1]

Explanation:

This creates a binary tree with only a root node with value -1.

Example 3:

Input:

preorder = [1,2], inorder = [2,1]

Output:

[1,2]

Explanation:

This creates a binary tree with root value 1 and left child 2.

Solutions

Recursive Approach with HashMap

Time: O(n)
Space: O(n)

Use the preorder traversal to determine the root nodes and the inorder traversal to determine the left and right subtrees. Use a HashMap for quick lookup of inorder indices.

Iterative Approach with Stack

Time: O(n)
Space: O(n)

Use a stack to simulate the recursive approach, processing nodes level by level while keeping track of the current position in both traversals.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Create a map for inorder traversal: {9:0, 3:1, 15:2, 20:3, 7:4}
  2. Start building the tree with root = 3 (preorder[0])
  3. Find the index of 3 in inorder: 1
  4. Left subtree: preorder[1:2], inorder[0:0] = [9], [9]
  5. Build left subtree of 3 recursively
  6. Root = 9 (preorder[1])
  7. No more elements in left subtree, return 9 as left child of 3
  8. Right subtree: preorder[2:4], inorder[2:4] = [20, 15, 7], [15, 20, 7]
  9. Build right subtree of 3 recursively
  10. Root = 20 (preorder[2])
  11. Find the index of 20 in inorder: 3
  12. Left subtree: preorder[3:3], inorder[2:2] = [15], [15]
  13. Build left subtree of 20 recursively
  14. Root = 15 (preorder[3])
  15. No more elements in subtree, return 15 as left child of 20
  16. Right subtree: preorder[4:4], inorder[4:4] = [7], [7]
  17. Build right subtree of 20 recursively
  18. Root = 7 (preorder[4])
  19. No more elements in subtree, return 7 as right child of 20
  20. Return 20 as right child of 3
  21. Final tree: [3,9,20,null,null,15,7]

Hints

Hint 1
The first element in preorder is always the root of the tree.
Hint 2
For each node in preorder, you can find its position in inorder to determine which elements are in its left subtree and which are in its right subtree.
Hint 3
Use a hash map to store the indices of elements in inorder for O(1) lookup.
Hint 4
Use recursion to build the left and right subtrees separately.

Video Tutorial

Construct Binary Tree from Preorder and Inorder Traversal - Recursive Solution

YouTube•Learn the Construct Binary Tree from Preorder and Inorder Traversal solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize how the binary tree is constructed using preorder and inorder traversals.

Key visualization elements:

  • current preorder node
  • current inorder node
  • left subtree
  • right subtree

Similar Questions

Serialize and Deserialize Binary Tree

Hard

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Asked By

AmazonGoogleMicrosoftFacebookBloombergAdobeAppleUber

Implementation Notes

This problem tests understanding of tree traversals and tree construction algorithms. It is a classic interview question that combines array manipulation, divide-and-conquer strategy, and binary tree concepts.