Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Two arrays describe the same binary tree:

  • Preorder visits each node before its children: root, left subtree, right subtree.
  • Inorder visits each node between its children: left subtree, root, right subtree.

The task is to rebuild and return the tree. Every value is unique, and the two arrays are guaranteed to describe the same tree.

The crucial distinction is that this is not necessarily a binary search tree. Values do not decide where nodes belong. Only their positions in the two traversals provide that information.

Deriving the structure

The first preorder value must be the root because preorder always visits a subtree’s root first. Finding that value in inorder then splits the remaining nodes into two groups:

inorder:  [everything in the left subtree] root [everything in the right subtree]

This immediately gives a recursive solution. Store every inorder value’s index in a hash table, use the next preorder value as each subtree root, and recurse over the corresponding inorder ranges. Each node is created once and each boundary lookup costs O(1), so the total time is O(n).

There is one practical issue in Python: a completely skewed tree can make the recursion depth O(n) and exceed the interpreter’s recursion limit. The implementation below preserves the same boundary idea but makes the pending ancestors explicit with a stack.

Start with the first preorder value as the root. The stack contains the path of ancestors whose construction is not yet complete, while inorder_index points to the next node that inorder says should finish:

  • If the stack’s top value is not inorder[inorder_index], that node has not reached its inorder position. The next preorder value must therefore begin or continue its left subtree, so it becomes the top node’s left child.
  • If the values match, the top node’s left subtree is complete. Pop it and any ancestors that also match successive inorder values. The next preorder value becomes the right child of the last node popped.

Each node is pushed once and popped once. The stack therefore performs the reconstruction in O(n) time without recursive calls.

Why the algorithm works

Consider the next value in preorder. It is always the root of the next subtree that has not been built.

When the current stack top does not match the next inorder value, inorder says some node must still appear before that ancestor. Those missing nodes can only belong to its left subtree. Preorder visits that subtree before moving right, so attaching the next value on the left is forced.

When the stack top does match, inorder has finished everything to that node’s left and is now visiting the node itself. Popping matching ancestors walks upward through every subtree that has just finished. Preorder’s next unbuilt subtree must then be the right subtree of the highest ancestor just completed, which is the last node popped.

These are the only two possible cases. Every attachment is forced by both traversal orders, so the final tree is the unique tree they describe.

Complexity

The reconstruction takes O(n) time because each node enters and leaves the stack at most once. Its stack uses O(h) space, where h is the tree height; this is O(n) in the worst case.

The production checks below also use sets to reject duplicates or mismatched values, making total auxiliary space O(n). Under LeetCode’s guaranteed-valid input contract, those checks can be removed and the reconstruction itself uses only O(h) auxiliary space.

Python solution

from __future__ import annotations

from collections.abc import Sequence


class TreeNode:
    """A node in a binary tree."""

    def __init__(
        self,
        value: int = 0,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = value
        self.left = left
        self.right = right


class BinaryTreeBuilder:
    """Build binary trees from compatible traversal sequences."""

    @classmethod
    def from_preorder_and_inorder(
        cls,
        preorder: Sequence[int],
        inorder: Sequence[int],
    ) -> TreeNode | None:
        """Return the unique tree described by preorder and inorder."""
        cls._validate_values(preorder, inorder)
        if not preorder:
            return None

        root = TreeNode(preorder[0])
        unfinished_ancestors = [root]
        inorder_index = 0

        for value in preorder[1:]:
            if inorder_index >= len(inorder):
                raise ValueError("The traversals do not describe the same tree.")

            next_node = TreeNode(value)
            current_parent = unfinished_ancestors[-1]

            if current_parent.val != inorder[inorder_index]:
                # Inorder has not reached the parent, so its left side is open.
                current_parent.left = next_node
            else:
                # Close every subtree that inorder says is complete. The next
                # preorder node starts the right subtree of the last one closed.
                while (
                    unfinished_ancestors
                    and inorder_index < len(inorder)
                    and unfinished_ancestors[-1].val == inorder[inorder_index]
                ):
                    current_parent = unfinished_ancestors.pop()
                    inorder_index += 1

                current_parent.right = next_node

            unfinished_ancestors.append(next_node)

        # Consume the final right boundary and reject incompatible orderings.
        while (
            unfinished_ancestors
            and inorder_index < len(inorder)
            and unfinished_ancestors[-1].val == inorder[inorder_index]
        ):
            unfinished_ancestors.pop()
            inorder_index += 1

        if unfinished_ancestors or inorder_index != len(inorder):
            raise ValueError("The traversals do not describe the same tree.")

        return root

    @staticmethod
    def _validate_values(
        preorder: Sequence[int],
        inorder: Sequence[int],
    ) -> None:
        """Check the requirements that make reconstruction unique."""
        if len(preorder) != len(inorder):
            raise ValueError("Traversal lengths must match.")

        preorder_values = set(preorder)
        inorder_values = set(inorder)
        if len(preorder_values) != len(preorder):
            raise ValueError("Node values must be unique.")
        if len(inorder_values) != len(inorder):
            raise ValueError("Node values must be unique.")
        if preorder_values != inorder_values:
            raise ValueError("Traversals must contain the same values.")


class Solution:
    """LeetCode-compatible entry point."""

    def buildTree(
        self,
        preorder: list[int],
        inorder: list[int],
    ) -> TreeNode | None:
        return BinaryTreeBuilder.from_preorder_and_inorder(preorder, inorder)

Interview follow-ups

How would you implement the recursive divide-and-conquer version?

Build a hash table from each value to its inorder index. Maintain one preorder cursor, and define a helper that receives an inclusive inorder range. The next preorder value is the range’s root; its hash-table position splits the range into left and right parts, which the helper builds in that order.

The cursor advances once per node, and the hash table prevents repeated linear searches, so the solution takes O(n) time and O(n) space for the map plus O(h) call-stack space. Its proof is especially direct and it is often the best version to derive first in an interview. In Python, the iterative version is safer when a skewed tree may contain more nodes than the recursion limit allows.

What if node values are not unique?

Plain preorder and inorder value sequences no longer identify one unique tree. An inorder value can match several positions, and different choices may produce different valid structures. For example, repeated equal values can make multiple trees produce exactly the same two sequences.

If nodes have distinct IDs in addition to display values, reconstruct with the IDs and keep the same O(n) approach. If only duplicate values are available, the requirements must change: return any valid tree, enumerate every valid tree, or report ambiguity. Trying candidate inorder positions requires backtracking and can take exponential time because the input no longer provides enough information to force each split.

How would the solution change for inorder and postorder traversals?

Postorder visits left, right, root, so its last value is the root. A recursive solution consumes postorder from right to left and builds the right subtree before the left subtree. The inorder position still divides the two sides, and a value-to-index map still gives O(n) time.

The iterative solution is symmetric as well: begin with the last postorder value, scan postorder backward, compare against inorder from right to left, and attach right children until an inorder boundary closes. Then pop completed ancestors and attach the next value on the left. The time remains O(n) and the stack remains O(h).

How would you verify that arbitrary input traversals are compatible?

Equal lengths, unique values, and equal value sets are necessary, but they are not sufficient. The relative orders may still contradict each other. During reconstruction, every node must eventually be popped in exactly the supplied inorder order. If the stack cannot match the next inorder value, or values remain after construction, the pair is invalid.

That is why the production implementation performs a final boundary-consumption check rather than trusting the set checks alone. Validation is still O(n) time and O(n) auxiliary space, dominated by the sets. With guaranteed-valid interview input, these defensive checks can be omitted for a shorter solution.

What if the interviewer asks for postorder output but not the tree itself?

The same recursive range decomposition can append each root after processing its left and right ranges, directly producing postorder without allocating TreeNode objects. The inorder index map and preorder cursor are unchanged; only the output action moves to the end of the helper.

This takes O(n) time, O(n) space for the output and index map, and O(h) recursion space. If modifying the input is allowed, some storage can be reused, but the n output values themselves are unavoidable.

Can the construction be parallelized?

After a root’s inorder position is known, its left and right subtrees are independent and can be built concurrently. The preorder segment sizes are determined by the inorder split, so each worker receives disjoint preorder and inorder ranges.

The total work stays O(n). The theoretical span becomes proportional to the tree height, but practical speedup depends on balance: a skewed tree exposes almost no parallelism. Thread creation and synchronization also overwhelm small subtrees, so a production implementation would parallelize only ranges above a size threshold and would usually use processes or native code for CPU-bound Python work.