Construct Binary Tree from Preorder and Inorder Traversal

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Given two integer arrays preorder and inorder that are the preorder and inorder traversals of the same binary tree with distinct values, rebuild and return the tree. A common warm-up in the same round: build a tree from a level-order list such as [8, 3, 10, 1, 6, null, 14], then return its preorder traversal.

    This problem tests whether you really understand what each traversal order tells you, not just how to write it. Preorder tells you which node is the root; inorder tells you which nodes are on each side of it. Original problem: LeetCode 105.

    Example

    The two lists describe exactly one tree: root 8, with 3 (children 1 and 6) on the left and 10 (right child 14) on the right.
    The two lists describe exactly one tree: root 8, with 3 (children 1 and 6) on the left and 10 (right child 14) on the right.
    Input:  preorder = [8, 3, 1, 6, 10, 14]
            inorder  = [1, 3, 6, 8, 10, 14]
    Output: [8, 3, 10, 1, 6, null, 14]       # the tree, in level order
    Input:  preorder = [5], inorder = [5]
    Output: [5]

    Constraints (assumed)

    • 1 ≤ n ≤ 3,000; all values are distinct.
    • Both arrays describe the same valid tree.

    What this question tests

    • Knowing what preorder (root first) and inorder (left, root, right) each reveal.
    • A clean divide-and-conquer recursion over index ranges, without copying subarrays.
    • Spotting the O(n²) trap (searching inorder each time) and fixing it with a hash map.

    Questions to ask first

    1. Are the values distinct? With duplicates the tree is not uniquely determined. (Here: distinct.)
    2. Are the inputs guaranteed to be consistent? (Here: yes; otherwise you'd validate.)
    3. How deep can the tree be? A 3,000-node chain means 3,000 levels of recursion.
    4. What should be returned: the root, or a serialised form? (Here: the root.)