Start learning free

LESSON 420 OF 539 · BINARY TREES

Build a Binary Tree from Preorder and Inorder in C#: O(n) Dictionary

Practice O(n) Read the full explanation

Two arrays describe the same binary tree:

  • preorder lists the values in preorder: first a node, then its whole left subtree, then its whole right subtree.
  • inorder lists the values in inorder: first a node's whole left subtree, then the node, then its whole right subtree.

All the values are different. Build the tree and return its root.

The tests print the tree you return level by level, from left to right, with null where a child is missing and the trailing nulls left out. For example, [1,2,null,3] is the tree with root 1, 2 as its left child and 3 as the left child of 2.

 

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
    3
   / \
  9   20
     /  \
    15   7

Explanation: preorder starts with 3, so 3 is the root. In inorder, 9 is left of 3 and 15, 20, 7 are right of it: 9 is the left subtree and 15, 20, 7 are the right subtree. The right subtree's values come next in preorder, starting with 20, its root; in inorder 15 is left of 20 and 7 is right of it.

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
Explanation: A single value is a tree with only a root.

Example 3:

Input: preorder = [1,2,3], inorder = [3,2,1]
Output: [1,2,null,3]
      1
     /
    2
   /
  3

Explanation: In inorder, every value comes before its parent, so each node has only a left child. The same preorder with inorder = [1,2,3] would give a line going right: [1,null,2,null,3].

 

Constraints:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • Every value is between -3000 and 3000, and the values are all different.
  • preorder and inorder are the preorder and inorder traversals of the same tree.
  • The tree is at most 400 levels deep.

Note:

The solution should run in O(n) time, where n is the number of values: build each node once, and find where a value sits in inorder with a Dictionary instead of a search.

STEP 1 OF 13
    Ctrl + Enter to check

    C# · BINARY TREES

    Construct Binary Tree From Preorder And Inorder Traversal in C#, explained

    Problem overview

    BuildTree receives two int[] arrays, preorder and inorder, the two traversals of the same binary tree with all values different, and returns the root of that tree. The lesson provides the TreeNode class (val, left, right and a constructor taking the value), as the starter code's comment shows.

    For preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7], the tree has 3 at the root, 9 as its left child, and 20 as its right child with children 15 and 7. Printed level by level, that is [3,9,20,null,null,15,7].

    Approach: preorder names the root, inorder splits the rest

    Two facts about the traversals do all the work:

    • In preorder, a node comes before its subtrees. So the first value is the root of the whole tree, and in general the next unused value is the root of the next subtree we build.
    • In inorder, a node sits between its left subtree and its right subtree. Find the root's position in inorder: everything to its left is the left subtree, everything to its right is the right subtree.

    So take the root from preorder, find it in inorder, and recursively build the left part and then the right part. Building the left subtree first matters: the left subtree's roots come right after this root in preorder, before any root of the right subtree. A single counter that moves forward through preorder therefore always points at the correct next root.

    The only slow part would be finding the root's position in inorder. Scanning for it every time costs O(n) per node, O(n^2) overall. Since all values are different, a Dictionary<int, int> from value to index, filled once, answers in constant time.

    Step by step

    1. Field inorderIndex: a Dictionary<int, int> created empty. A field is visible to every method of the class, so the helper can read it.
    2. Field preIndex: an int starting at 0, the position in preorder of the next root.
    3. Fill the map in BuildTree with a loop over i from 0 while i < inorder.Length, setting inorderIndex[inorder[i]] = i.
    4. Start the recursion: return Build(preorder, 0, inorder.Length - 1). The whole of inorder is the whole tree.
    5. Write Build(int[] preorder, int lo, int hi). The pair lo and hi marks the stretch of inorder holding this subtree's values; every subtree fills one unbroken stretch.
    6. Empty range: if lo > hi, return null. Below a leaf, both ranges are empty, and this is where the recursion stops.
    7. Take the root: value = preorder[preIndex], then preIndex++.
    8. Create the node with new TreeNode(value).
    9. Locate the root in inorder: mid = inorderIndex[value]. Indexes lo to mid - 1 are the left subtree, and mid + 1 to hi the right.
    10. Build the left subtree first, with range lo to mid - 1, and store it in node.left.
    11. Build the right subtree with range mid + 1 to hi and store it in node.right. By then the left subtree has used up all its roots, so preIndex points at this subtree's root.
    12. Return node.

    The solution in C#

    class Solution {
    Dictionary<int, int> inorderIndex = new Dictionary<int, int>();
    int preIndex = 0;

    public TreeNode Build(int[] preorder, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        int value = preorder[preIndex];
        preIndex++;
        TreeNode node = new TreeNode(value);
        int mid = inorderIndex[value];
        node.left = Build(preorder, lo, mid - 1);
        node.right = Build(preorder, mid + 1, hi);
        return node;
    }

    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.Length; i++) {
            inorderIndex[inorder[i]] = i;
        }
        return Build(preorder, 0, inorder.Length - 1);
    }
}

    C# details worth knowing:

    • Fields keep the state between calls. preIndex must survive from one recursive call to the next, so it is a field and not a local variable. Passing it as a plain int parameter would copy it, and the left call's progress would be lost to the right call. (A ref int parameter would also work.) The consequence is that one Solution object builds one tree: a second call of BuildTree on the same object would start with preIndex wherever the first stopped.
    • The indexer inorderIndex[inorder[i]] = i adds or overwrites. Assigning through the indexer is fine for a new key. Reading a key that isn't there throws KeyNotFoundException, which can't happen here because every value of preorder is also in inorder.
    • inorder.Length is a property of an array, with no parentheses; Count is the equivalent for a List<T>.
    • Arrays are passed by reference, so passing preorder down the recursion copies nothing.

    Complexity

    Time: O(n). Filling the dictionary visits each index once. Build creates each node exactly once and does constant work per node: one array read, one dictionary lookup and two calls. The calls that return null number n + 1 in total.

    Space: O(n). The dictionary holds n entries. The recursion goes as deep as the tree is tall, up to n levels for a tree that is a straight line (the lesson limits depth to 400).

    Edge cases and common mistakes

    • A single node. preorder = [-1], inorder = [-1] gives the tree [-1]. Negative values work like any other, because they are only used as dictionary keys.
    • All left children. preorder = [1,2,3] with inorder = [3,2,1] gives [1,2,null,3]. With inorder = [1,2,3] instead, the same preorder gives a line going right, [1,null,2,null,3].
    • Building the right subtree first. The counter would point at the left subtree's root while the code believes it is reading the right subtree's, and the tree would be wrong. The order of the two recursive calls is fixed by preorder.
    • Using the wrong range for the right half. The right subtree is mid + 1 to hi, not mid to hi; mid is the root itself.
    • Searching inorder with a loop. It works but costs O(n) per node. With a dictionary, each lookup is constant time.

    Testing

    Running BuildTree and printing the result level by level gives:

    preorderinorderTree
    [3,9,20,15,7][9,3,15,20,7][3,9,20,null,null,15,7]
    [-1][-1][-1]
    [1,2,3][3,2,1][1,2,null,3]
    [1,2,3][1,2,3][1,null,2,null,3]

    For the first input, the calls of Build take their roots in this order, with the stretch of inorder each one covers:

    root=3  lo=0 hi=4  mid=1
root=9  lo=0 hi=0  mid=0
root=20 lo=2 hi=4  mid=3
root=15 lo=2 hi=2  mid=2
root=7  lo=4 hi=4  mid=4

    The roots come out in exactly the order of preorder, which is why one forward-moving counter is enough.

    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free