Reconstructing a Binary Tree from Preorder and Postorder Traversals

Problem Description

Given two integer arrays, preorder and postorder, representing the preorder and postorder traversals of a binary tree with distinct values, the task is to reconstruct and return the binary tree.

Naive Approach

A brute-force approach would involve recursively searching for the left and right subtrees based on the given preorder and postorder arrays. We know the first element in preorder is always the root. We find this root's position in the postorder array. All elements before the root's position in the postorder represent the left subtree, while the remaining elements (excluding the root) represent the right subtree. This can be done recursively.

However, this approach typically involves repeated searching within arrays, leading to a less efficient solution.

Optimal Approach: Divide and Conquer

The optimal approach leverages the properties of preorder and postorder traversals using a divide-and-conquer strategy. The core idea is to recursively build the tree:

1. The first element in the preorder array is always the root of the current subtree.
2. The element immediately after the root in preorder is the root of the left subtree.
3. Find the index of the left subtree's root in postorder. This allows determining the size of the left subtree.
4. Knowing the size of the left subtree, the boundaries for the left and right subtrees in both preorder and postorder can be defined.
5. Recursively construct the left and right subtrees.

Algorithm:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def construct_from_pre_post(preorder, postorder):
    if not preorder or not postorder:
        return None

    root_val = preorder[0]
    root = TreeNode(root_val)

    if len(preorder) == 1:
        return root

    left_root_val = preorder[1]
    left_root_index_in_post = postorder.index(left_root_val)

    left_size = left_root_index_in_post + 1

    root.left = construct_from_pre_post(
        preorder[1 : 1 + left_size],
        postorder[:left_size],
    )

    root.right = construct_from_pre_post(
        preorder[1 + left_size :],
        postorder[left_size:-1],
    )

    return root


# Example usage:
preorder = [1, 2, 4, 5, 3, 6, 7]
postorder = [4, 5, 2, 6, 7, 3, 1]
tree = construct_from_pre_post(preorder, postorder)

# A simple function to print the inorder traversal for verification
def inorder_traversal(root):
  if root:
    inorder_traversal(root.left)
    print(root.val, end=" ")
    inorder_traversal(root.right)

print("Inorder Traversal:")
inorder_traversal(tree) # Output: 4 2 5 1 6 3 7

Edge Cases

• Empty Input: If either preorder or postorder is empty, return None.
• Single Node: If the length of the arrays is 1, create a single-node tree and return it.
• Invalid Input: Although the problem states that the inputs are guaranteed to be valid, in a real-world scenario, it's important to handle potential inconsistencies between the preorder and postorder arrays (e.g., different lengths, different sets of values).

Time and Space Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once during the construction process. The index() operation in Python takes O(N) time in the worst case. However, if we use a hash map to store indices of elements in the postorder array, we can reduce the lookup time to O(1), making the overall time complexity O(N).
• Space Complexity: O(N) due to the recursive call stack. In the worst-case scenario (skewed tree), the recursion depth can be equal to the number of nodes, resulting in O(N) space. Additionally, the tree itself requires O(N) space.