Given the preorder and inorder traversal sequences of a binary tree, the task is to rebuild the original tree. Below are three distinct strategies, each with its own trade-offs, followed by concise Python implementations.

Approach 1 – Straightforward Recursion

The first element in preorder is always the root. Locate this value inside inorder; everything to the left belongs to the left subtree, everything to the right to the right subtree. Recurse on the two resulting sub-arrays. The search for the root inside inorder is linear, giving an overall complexity of O(n²) in the worst case (degenerate tree). Space usage is O(h) due to the call stack.

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

def build(pre, ino):
    if not pre:
        return None
    root = Node(pre[0])
    idx = ino.index(pre[0])
    root.left  = build(pre[1:1+idx], ino[:idx])
    root.right = build(pre[1+idx:], ino[idx+1:])
    return root

Approach 2 – Recursion with Hash-Map Lookup

Pre-compute a dictionary that maps each value to its index in inorder. This reduces the root lookup to O(1). Instead of slicing arrays, pass explicit boundaries (l, r) across recursive calls. The algorithm now runs in O(n) time and O(n) extra space (hash table plus recursion).

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

def build(pre, ino):
    pos = {v: i for i, v in enumerate(ino)}
    def helper(root_idx, left, right):
        if left > right:
            return None
        node = Node(pre[root_idx])
        mid = pos[pre[root_idx]]
        node.left  = helper(root_idx + 1, left, mid - 1)
        node.right = helper(root_idx + mid - left + 1, mid + 1, right)
        return node
    return helper(0, 0, len(pre) - 1)

Approach 3 – Iterative Stack Method

Maintain a stack that always contains the current path from the root downwards. Iterate over preorder; each new node is either the left child of the previous node (if its value has not yet appeared in inorder) or the right child of some ancestor (determined by matching against inorder). This yields an O(n) time, O(h) space solutoin without recursion.

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

def build(pre, ino):
    if not pre:
        return None
    root = Node(pre[0])
    stack, idx = [root], 0
    for val in pre[1:]:
        node = Node(val)
        if stack[-1].val != ino[idx]:
            stack[-1].left = node
        else:
            while stack and stack[-1].val == ino[idx]:
                last = stack.pop()
                idx += 1
            last.right = node
        stack.append(node)
    return root

Each snippet can be tested with the same input:

pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
tree = build(pre, ino)
# in-order walk to verify
def walk(n):
    return walk(n.left) + [n.val] + walk(n.right) if n else []
print(walk(tree))  # → [9, 3, 15, 20, 7]