LeetCode 101: 105 Construct Binary Tree from Preorder and Inorder Traversal

LeetCode Problem: 105. Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

Problem Description:

Given the preorder and inorder traversal arrays, construct the corresponding binary tree and return its root node.

Example 1:

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

Example 2:

Input:
preorder = [-1]
inorder = [-1]
Output:
   -1

Original Code (Recursive Approach):

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:  # If either preorder or inorder is empty, return None
            return None

        root = TreeNode(preorder[0])  # The first element of preorder is the root node
        idx = inorder.index(preorder[0])  # Find the index of the root in the inorder traversal

        # Recursively construct the left and right subtrees
        root.left = self.buildTree(preorder[1: idx + 1], inorder[:idx])
        root.right = self.buildTree(preorder[idx + 1:], inorder[idx + 1:])

        return root  # Return the constructed tree's root node

Line-by-Line Explanation and Example Execution:

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
- Defines the main function buildTree, which accepts lists for preorder and inorder traversals and returns the root node of the constructed binary tree.
if not preorder or not inorder:
- Checks if either the preorder or inorder traversal is empty. If so, it returns None, indicating that no tree exists.
root = TreeNode(preorder[0])
- Creates the root node of the tree, using the first element of the preorder traversal.
idx = inorder.index(preorder[0])
- Finds the index of the root node’s value in the inorder traversal to determine the ranges for the left and right subtrees.
root.left = self.buildTree(preorder[1: idx + 1], inorder[:idx])
- Recursively constructs the left subtree:
  - The range for the preorder traversal is preorder[1: idx + 1], which includes all nodes that are part of the left subtree.
  - The range for the inorder traversal is inorder[:idx], which consists of all nodes to the left of the root node.
root.right = self.buildTree(preorder[idx + 1:], inorder[idx + 1:])
- Recursively constructs the right subtree:
  - The range for the preorder traversal is preorder[idx + 1:], which includes nodes that are part of the right subtree.
  - The range for the inorder traversal is inorder[idx + 1:], which consists of all nodes to the right of the root node.
return root
- Returns the constructed tree’s root node.

Example Execution:

Assuming we have the following preorder and inorder traversals:

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

Execution steps:

Initial Call:
- root = 3 (the first element of the preorder traversal).
- idx = 1 (the index of root node 3 in the inorder traversal).
Constructing the Left Subtree:
- Calls buildTree(preorder[1:2], inorder[:1]), which is buildTree([9], [9]).
  - Creates the left subtree root node 9 (the first element of the preorder traversal).
  - No further nodes are left, returns 9.
Constructing the Right Subtree:
- Calls buildTree(preorder[2:], inorder[2:]), which is buildTree([20, 15, 7], [15, 20, 7]).
  - root = 20 (the first element of the preorder traversal).
  - idx = 1 (the index of root node 20 in the inorder traversal).
Constructing the Right Subtree’s Left Subtree:
- Calls buildTree(preorder[1:2], inorder[:1]), which is buildTree([15], [15]).
  - Creates the left subtree root node 15, returns 15.
Constructing the Right Subtree’s Right Subtree:
- Calls buildTree(preorder[2:], inorder[2:]), which is buildTree([7], [7]).
  - Creates the right subtree root node 7, returns 7.
Final Result:
- The constructed tree is:
```
3
/ \
9   20
/  \
15   7
```

Time Complexity Analysis:

Time Complexity: O(n^2)
- In each recursive call, the inorder.index() method finds the index of the root, which takes O(n) time. In the worst case, this leads to O(n^2) overall.

Space Complexity Analysis:

Space Complexity: O(h)
- Where h is the height of the tree. The depth of the recursive call stack can go up to h.

Tips and Warnings:

Edge Cases:
- Consider cases where the preorder or inorder traversal is empty.
Understanding Recursion:
- Ensure you understand how to construct the tree based on the preorder and inorder traversals.
Optimize Index Lookup:
- Using a hash table to store indices of the inorder traversal can improve the lookup time, reducing the overall time complexity to O(n).

Optimized Code Example Using Hash Table:

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        inorder_index = {val: idx for idx, val in enumerate(inorder)}  # Create a map of inorder values to indices

        def helper(pre_start, pre_end, in_start, in_end):
            if pre_start > pre_end or in_start > in_end:
                return None

            root_val = preorder[pre_start]  # The value of the current root
            root = TreeNode(root_val)  # Create the root node

            idx = inorder_index[root_val]  # Get the index of the root in inorder

            # Recursively construct left and right subtrees
            root.left = helper(pre_start + 1, pre_start + (idx - in_start), in_start, idx - 1)
            root.right = helper(pre_start + (idx - in_start) + 1, pre_end, idx + 1, in_end)

            return root

        return helper(0, len(preorder) - 1, 0, len(inorder) - 1)  # Start from the root

Summary

Recursive Method: Effectively constructs a binary tree from preorder and inorder traversals, with a time complexity of O(n) (using hash table optimization) and a space complexity of O(h).
Clear and Understandable: The code is straightforward and easy to understand, suitable for handling this type of problem.

Application Tips

Choose Appropriate Methods:
- Select the method best suited to specific problem requirements to ensure efficiency and readability.
Handle Edge Cases:
- Always consider edge cases in algorithm design to avoid potential errors.
Optimize Space Usage:
- When handling large datasets, consider using space-efficient algorithms.

Post Views: 35

CODEBITWAVE