Start learning free

LESSON 417 OF 536 · BINARY TREES

Construct Binary Tree from Preorder and Inorder in Java: O(n)

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 HashMap instead of a search.

STEP 1 OF 13
    Ctrl + Enter to check

    JAVA · BINARY TREES

    Construct Binary Tree From Preorder And Inorder Traversal in Java, explained

    Problem overview

    The method buildTree receives two arrays, preorder and inorder, which list the values of the same binary tree in two different orders, and returns the root of that tree. All values are different. The lesson provides the TreeNode class, with val, left, right and a constructor that takes the value.

    In preorder a node comes first, then its whole left subtree, then its whole right subtree. In inorder the left subtree comes first, then the node, then the right subtree.

    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 15 and 7 below 20. Level by level, the tests print it as [3,9,20,null,null,15,7].

    Approach: preorder names the roots, inorder splits the sides

    Each traversal alone is ambiguous. The two together are enough, because they carry different information:

    • The first value of preorder is the root of the whole tree.
    • In inorder, everything left of that root belongs to its left subtree and everything right of it to its right subtree.

    That splits one problem into two smaller ones of the same kind. In the example, 3 is the root. In inorder, the value 9 is left of 3, so 9 alone is the left subtree, and 15, 20, 7 are the right subtree. The right subtree's root is the next unused value of preorder, which is 20, and the same split applies again.

    The root of each subtree is always the next unused value of preorder, as long as the code builds the left subtree completely before the right one. That order is exactly how preorder lists the nodes, so a single counter that moves forward through preorder is all the bookkeeping needed.

    The only repeated question is "where does this value sit in inorder?". Scanning for it each time would cost O(n) per node and O(n²) overall for a tree shaped like a chain. A HashMap from value to index, filled once, answers in constant time, which gives O(n) overall. It works because the values are all different.

    Step by step

    1. Keep a map from value to inorder position in a field, inorderIndex, a Map<Integer, Integer> starting as an empty HashMap. A field is visible to the helper method too.
    2. Keep a counter in a field, preIndex, starting at 0: the position in preorder of the next root to use.
    3. Fill the map in buildTree with a loop over the indices of inorder, storing each value with its index. This costs O(n) once.
    4. Start the recursion by returning build over the whole of inorder, from index 0 to inorder.length - 1.
    5. Declare build(preorder, lo, hi). The pair lo and hi is the stretch of inorder that holds this subtree's values. Every subtree fills one unbroken stretch, so two numbers describe it.
    6. Return null for an empty range, lo > hi. This is where the recursion ends, below the leaves.
    7. Take the next root: read preorder[preIndex] into value and advance preIndex.
    8. Create the node for that value.
    9. Find mid, the root's position in inorder, with inorderIndex.get(value).
    10. Build the left subtree from the range lo to mid - 1 and attach it as node.left. This must come first, because the left subtree's roots follow this node in preorder.
    11. Build the right subtree from mid + 1 to hi as node.right. By now the left side has used all of its roots, so preIndex points at the right subtree's root.
    12. Return the node.

    For the example, the calls run in this order (lo and hi are positions in inorder):

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

    The roots 3, 9, 20, 15, 7 come out in exactly the order of preorder.

    The solution in Java

    class Solution {
    Map<Integer, Integer> inorderIndex = new HashMap<>();
    int preIndex = 0;

    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.get(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.put(inorder[i], i);
        }
        return build(preorder, 0, inorder.length - 1);
    }
}

    Java details worth a closer look:

    • Unboxing. inorderIndex.get(value) returns an Integer, and assigning it to an int unboxes it automatically. If the key were missing, get would return null and the unboxing would throw a NullPointerException. The lesson guarantees that both arrays hold the same values, so every lookup succeeds.
    • Autoboxing in put. inorderIndex.put(inorder[i], i) wraps both ints into Integer objects. Map keys can't be primitives.
    • Fields shared by the methods. preIndex is changed inside build and stays changed across the recursive calls, which is what makes the single counter work. Passing it as a parameter would give each call its own copy.
    • Fields live as long as the object. A second call of buildTree on the same Solution object would start with preIndex still at its old value and fail. Each call needs a fresh object, or the method would have to reset preIndex and clear the map first.
    • Left before right. The two recursive calls are statements in a fixed order. Swapping them builds the wrong tree, because the right subtree would take the left subtree's roots from preorder.

    Complexity

    Time: O(n). Filling the map takes n steps. Each value becomes exactly one node, and each node costs one map lookup and a constant amount of other work. The calls that return null number n + 1, one for each missing child.

    Space: O(n). The map holds n entries and the tree itself has n nodes. The recursion adds a stack as deep as the tree, at most 400 levels in this lesson.

    Edge cases and common mistakes

    • A single value. preorder = [-1] and inorder = [-1] give the tree [-1]: the root's two ranges are empty and both children are null.
    • Only left children. preorder = [1,2,3] with inorder = [3,2,1] gives [1,2,null,3]: each root sits at the right end of its range, so the right range is always empty. With inorder = [1,2,3] the same preorder gives [1,null,2,null,3], a line going right.
    • Range arithmetic. The left range ends at mid - 1 and the right one starts at mid + 1. Using mid in either one puts the root into its own subtree and the recursion never ends.
    • Building right first. The counter then reads the wrong roots, as described above.
    • Searching instead of mapping. A loop that looks for value in inorder returns the right answer but makes the solution O(n²) on a chain-shaped tree.
    • Using the array length for the right bound. The last valid index is inorder.length - 1. Passing inorder.length makes the first call's range too large.

    Testing

    • preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] gives [3,9,20,null,null,15,7].
    • preorder = [-1], inorder = [-1] gives [-1].
    • preorder = [1,2,3], inorder = [3,2,1] gives [1,2,null,3].
    • preorder = [1,2,3], inorder = [1,2,3] gives [1,null,2,null,3].
    • preorder = [1,2,3], inorder = [2,1,3] gives [1,2,3].
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free