Tree Construction and Reconstruction

Reconstructing a Binary Tree from Traversals

LeetCode 105 gives you two arrays: preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7]. From these two traversals, reconstruct the original binary tree.

This is a classic problem that tests your understanding of how tree traversals encode structural information. A preorder traversal visits the root first, then the left subtree, then the right subtree. An inorder traversal visits the left subtree, then the root, then the right subtree. Neither traversal alone is enough to uniquely determine the tree, but together they contain all the information needed.

The Key Insight: Splitting Left and Right

The first element of the preorder array is always the root of the tree. In our example, 3 is the root. Now look at the inorder array: [9, 3, 15, 20, 7]. Everything to the left of 3 in the inorder array belongs to the left subtree, and everything to the right belongs to the right subtree.

So the left subtree contains the inorder sequence [9], and the right subtree contains [15, 20, 7]. The left subtree has 1 node, the right subtree has 3 nodes.

Now we apply the same logic recursively. The next element in preorder after the root is 9. This must be the root of the left subtree. In the inorder slice [9], there is nothing to the left or right of 9, so it is a leaf node.

The next element in preorder is 20. This is the root of the right subtree. In the inorder slice [15, 20, 7], everything left of 20 is [15] (left subtree of 20) and everything right is [7] (right subtree of 20).

Continuing: 15 is a leaf (next in preorder, nothing left or right in its inorder slice), and 7 is a leaf.

The reconstructed tree is:

3 / \ 9 20 / \ 15 7

Why Both Traversals Are Needed

Consider the preorder [1, 2, 3]. Without an inorder traversal, this could be many different trees. Node 1 is the root, but is 2 a left child or right child? Is 3 a child of 2 or of 1? The inorder traversal resolves these ambiguities because it tells us exactly which nodes are to the left and right of each root.

The one exception is binary search trees, where the BST property itself provides the information that inorder normally gives. We will return to this case later.

Using a Hashmap for $O(1)$ Lookup

In the naive approach, finding the root's position in the inorder array takes $O(n)$ time per recursive call, leading to $O(n^2)$ total time. We can precompute a hashmap that maps each value to its index in the inorder array, giving $O(1)$ lookup and reducing the overall time to $O(n)$.

Using an Iterator Instead of Array Slicing

Rather than slicing the preorder array into left and right portions at each step, we can use an iterator that walks through preorder from left to right. Each call to the recursive function consumes the next element from the iterator as the current root.

This works because of a beautiful alignment: the preorder traversal visits the root, then the entire left subtree, then the entire right subtree. If we build the left subtree first (which consumes all the preorder elements belonging to the left subtree) and then build the right subtree, the iterator naturally advances to the correct position. We never need to compute how many elements belong to each subtree.

Code: Build Tree from Preorder and Inorder

def build_tree(preorder, inorder):
    idx_map = {val: i for i, val in enumerate(inorder)}
    pre_iter = iter(preorder)

    def build(lo, hi):
        if lo > hi:
            return None
        val = next(pre_iter)
        mid = idx_map[val]
        node = TreeNode(val)
        node.left = build(lo, mid - 1)
        node.right = build(mid + 1, hi)
        return node

    return build(0, len(inorder) - 1)

The lo and hi parameters define the range within the inorder array that the current subtree spans. When lo > hi, the range is empty, meaning there is no subtree here, so we return None. Otherwise, we consume the next preorder element as the root, find its position mid in the inorder array, and recurse. The left subtree covers inorder indices lo to mid - 1, and the right subtree covers mid + 1 to hi.

The order matters: we must build the left subtree before the right subtree, because that matches the order in which preorder visits nodes. The iterator will advance through the left subtree's nodes first, then the right subtree's nodes.

From Inorder and Postorder

LeetCode 106 applies the same idea with one twist: building a tree from inorder and postorder. In a postorder traversal, the root is the last element (not the first). And because postorder visits nodes in the order left-right-root, if we read postorder from right to left, we get root-right-left. So we build the right subtree first, then the left subtree.

Consider inorder = [9, 3, 15, 20, 7] and postorder = [9, 15, 7, 20, 3]. The last element of postorder is 3, which is the root. We find 3 in inorder at index 1, splitting into left subtree [9] and right subtree [15, 20, 7].

Now reading postorder from right to left: after 3, the next element is 20, which is the root of the right subtree. Then 7 and 15 are the children. Then 9 is the left subtree.

Code: Build Tree from Inorder and Postorder

def build_tree(inorder, postorder):
    idx_map = {val: i for i, val in enumerate(inorder)}
    post_iter = reversed(postorder)

    def build(lo, hi):
        if lo > hi:
            return None
        val = next(post_iter)
        mid = idx_map[val]
        node = TreeNode(val)
        # Build right subtree FIRST (postorder reversed gives root-right-left)
        node.right = build(mid + 1, hi)
        node.left = build(lo, mid - 1)
        return node

    return build(0, len(inorder) - 1)

The only differences from the preorder version are: we iterate postorder in reverse, and we build the right subtree before the left subtree. Everything else is identical.

BST from Preorder Alone

For LeetCode 1008, you must reconstruct a BST from its preorder traversal alone. For binary search trees, we do not need an inorder traversal at all. The BST property tells us that all values in the left subtree are less than the root, and all values in the right subtree are greater. This is the same information that the inorder traversal normally provides.

Given preorder = [8, 5, 1, 7, 10, 12], we know 8 is the root. Values less than 8 (that is, 5, 1, 7) belong to the left subtree. Values greater than 8 (that is, 10, 12) belong to the right subtree.

Instead of finding the split point explicitly, we can use an upper-bound approach. We walk through the preorder array with an iterator and use a bound parameter to determine when we have left the current subtree. Each recursive call takes the current upper bound. If the next value in the iterator exceeds the bound, we know we have left this subtree and return None.

Code: BST from Preorder

def bst_from_preorder(preorder):
    idx = [0]

    def build(bound):
        if idx[0] == len(preorder) or preorder[idx[0]] > bound:
            return None
        val = preorder[idx[0]]
        idx[0] += 1
        node = TreeNode(val)
        node.left = build(val)       # left children must be < val
        node.right = build(bound)    # right children must be < ancestor bound
        return node

    return build(float('inf'))

When building the left subtree, the upper bound is the current node's value (left children must be smaller). When building the right subtree, the upper bound is whatever bound was passed to us from above (right children must still be less than the nearest ancestor whose left subtree we are in).

For example, starting with bound = infinity, we read 8 and create the root. We recurse left with bound = 8. We read 5 (less than 8, so it belongs here) and create a node. We recurse left with bound = 5. We read 1 (less than 5) and create a leaf. We recurse left with bound = 1, but the next value is 7 which exceeds 1, so we return None. We recurse right with bound = 5, and 7 exceeds 5, so we return None. Back at node 5, we recurse right with bound = 8. We read 7 (less than 8) and create a leaf.

Back at the root 8, we recurse right with bound = infinity. We read 10 and create a node. Its left subtree with bound = 10 finds 12 > 10, so None. Its right subtree with bound = infinity reads 12 and creates a leaf.

Serialize and Deserialize a Binary Tree

LeetCode 297 tackles serialization, which converts a tree to a string, and deserialization, which reconstructs the tree from that string. The cleanest approach uses preorder traversal with explicit null markers. When we encounter a null child, we record a sentinel value (like "null" or "#") instead of silently skipping it. This makes the encoding unambiguous: we do not need a second traversal.

For the tree [1, 2, 3, null, null, 4, 5], the serialization is "1,2,null,null,3,4,null,null,5,null,null". Each node is followed by its left and right subtrees. Null markers tell us exactly where a subtree ends.

Deserialization reads the tokens one by one. Each token is either a value (create a node, recurse for its children) or a null marker (return None). Because we recorded every null, the structure is fully determined by the single serialized sequence.

Code: Serialize and Deserialize

class Codec:
    def serialize(self, root):
        tokens = []

        def dfs(node):
            if not node:
                tokens.append("null")
                return
            tokens.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(tokens)

    def deserialize(self, data):
        tokens = iter(data.split(","))

        def dfs():
            val = next(tokens)
            if val == "null":
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()

The serialize function performs a preorder DFS, appending each value and "null" for missing children. The deserialize function uses an iterator over the tokens. It reads the next token: if it is "null", return None; otherwise, create a node and recursively build its left and right children. The iterator naturally advances through the tokens in the correct order because deserialization follows the same preorder sequence as serialization.

This approach handles any binary tree, not just BSTs. It works for trees with duplicate values, negative values, or any other node values. The null markers make the structure explicit, so no second traversal or additional information is needed.

Complexity Analysis

All of the reconstruction algorithms visit each node exactly once, so the time complexity is $O(n)$. The hashmap construction for inorder lookup is also $O(n)$.

The space complexity is $O(n)$ for the hashmap and $O(h)$ for the recursion stack, where h is the height of the tree. In the worst case (a skewed tree), h = n, so space is $O(n)$ overall. For balanced trees, the recursion stack is $O(\log n)$, but the hashmap still takes $O(n)$.

For serialization and deserialization, the serialized string takes $O(n)$ space (it contains one entry per node plus one entry per null pointer, which is at most n + 1 nulls). Time is $O(n)$ for both operations.

The BST-from-preorder solution does not need a hashmap at all, so its space complexity is just $O(h)$ for the recursion stack. The upper-bound technique eliminates the need for any auxiliary data structure, making it the most space-efficient of the reconstruction algorithms.

Recognizing this pattern

You're probably looking at tree construction/reconstruction when:

• The input is one or two traversal sequences (preorder, inorder, postorder, level-order) and the output is the tree itself.
• The problem asks you to serialize a tree to a string and later rebuild the exact structure.
• You need to build a BST from a sorted array or an arbitrary sequence using value-range bounds.
• The hard part is identifying the root in each recursive step (first of preorder, last of postorder, head of queue) and splitting the remaining sequence into left and right subtree segments.

Common templates:

• Preorder + inorder with index map: root is first of preorder, inorder split gives subtree sizes. Example: Construct Binary Tree from Preorder and Inorder Traversal.
• Postorder + inorder: root is last of postorder, build right subtree before left. Example: Construct Binary Tree from Inorder and Postorder Traversal.
• BST from preorder with upper bound: use a value bound to decide when to stop descending. Example: Construct Binary Search Tree from Preorder Traversal.
• Serialize / deserialize with sentinels: encode nulls explicitly so a single preorder string round-trips. Example: Serialize and Deserialize Binary Tree.