{x}
blog image

Construct Binary Tree from Preorder and Inorder Traversal

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.

Solution Explanation: Construct Binary Tree from Preorder and Inorder Traversal

This problem involves constructing a binary tree given its preorder and inorder traversal sequences. The solution uses a recursive depth-first search (DFS) approach.

Understanding Preorder and Inorder Traversal:

  • Preorder traversal: Visits the root node first, then recursively traverses the left subtree, and finally the right subtree. The sequence is [Root, Left Subtree, Right Subtree].

  • Inorder traversal: Visits the left subtree recursively, then the root node, and finally the right subtree recursively. The sequence is [Left Subtree, Root, Right Subtree].

Algorithm:

  1. Base Case: If the number of nodes n is 0 or less, return null (or None in Python). This indicates an empty subtree.

  2. Root Node: The first element of the preorder array is always the root node of the current subtree.

  3. Root Index in Inorder: Locate the index k of the root node in the inorder array. This index divides the inorder array into two parts: the left subtree (elements before k) and the right subtree (elements after k).

  4. Subtree Sizes: The number of nodes in the left subtree is k - j, and the number of nodes in the right subtree is n - 1 - (k - j), where j is the starting index of the current inorder subarray.

  5. Recursive Calls: Recursively call the function to construct the left and right subtrees using appropriate segments of the preorder and inorder arrays.

  6. Tree Construction: Create a new TreeNode with the root node's value and the constructed left and right subtrees as children. Return this TreeNode.

Time and Space Complexity:

  • Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed exactly once.

  • Space Complexity: O(N) in the worst case (a skewed tree). This is due to the recursive call stack. In the average case, space complexity might be lower, depending on the tree structure. The hash table (or map) used to speed up the root index lookup in the inorder array adds a negligible O(N) space overhead.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript):

The code examples in the original response demonstrate the algorithm effectively. The key improvement is using a hash table (dictionary in Python) or a map in other languages to quickly find the index of the root node in the inorder array. This avoids repeated linear searches and optimizes the time complexity to O(N). The solutions also handle the edge case of empty input arrays. The variations for handling duplicates are also provided.

Note: The provided code snippets are complete and functional. They include the necessary TreeNode class definitions or structures and demonstrate how to build the tree recursively based on the preorder and inorder arrays.