Start learning free

LESSON 421 OF 540 · BINARY TREES

Build a Binary Tree from Preorder and Inorder in Scala: 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 mutable.Map instead of a search.

STEP 1 OF 13
    Ctrl + Enter to check

    SCALA · BINARY TREES

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

    Problem overview

    buildTree receives two arrays, preorder and inorder, which list the values of the same binary tree in two different orders, and returns the tree's root as a TreeNode. The lesson provides that class: new TreeNode(value) creates a node, and its left and right fields start as null and can be assigned. All values are different.

    • Preorder lists a node first, then its whole left subtree, then its whole right subtree.
    • Inorder lists a node's whole left subtree, then the node, then its whole right subtree.

    For preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7] the answer is the tree with root 3, left child 9, and right child 20 whose children are 15 and 7. Printed level by level, as the tests do, that is [3,9,20,null,null,15,7].

    Approach: preorder picks the root, inorder splits the rest

    The first value of preorder is always the root. Find that value in inorder: everything to its left belongs to the left subtree, and everything to its right belongs to the right subtree. Each of those two parts is a smaller instance of the same problem, so recursion fits.

    The roots of the smaller trees come from preorder too. After the root, preorder lists the whole left subtree and then the whole right subtree. So if the code builds the left subtree first and always takes the next unused value of preorder as the next root, each subtree finds its root at the right moment. That needs only a counter that moves forward through preorder.

    The slow part would be finding the root in inorder again for every node, which is a linear search each time. Because all values are different, each value has one position, so a map from value to position, built once, answers in constant time. That is what brings the total to O(n).

    The recursion works on ranges of inorder rather than copies of the arrays: lo and hi are the first and last index of the part that holds the current subtree's values. A range with lo > hi is empty and stands for no tree.

    Step by step

    1. Keep the positions. Declare a field inorderIndex, an empty scala.collection.mutable.HashMap[Int, Int](). As a field, the helper can read it as well.
    2. Keep the counter. Declare a var preIndex = 0: the position in preorder of the next root to use.
    3. Fill the map. In buildTree, loop over inorder.indices, and for each index i store inorderIndex(inorder(i)) = i. This is one pass, O(n).
    4. Start the recursion. Return build(preorder, 0, inorder.length - 1): the whole of inorder is the whole tree.
    5. Write the helper's header. build takes the preorder array and two Ints, lo and hi, and returns a TreeNode.
    6. Stop on an empty range. If lo > hi, return null. Below every leaf, both ranges are empty, so this is where the recursion ends.
    7. Take the next root. Read preorder(preIndex) into value and move preIndex forward by one.
    8. Create the node with new TreeNode(value).
    9. Find the root in inorder. mid = inorderIndex(value). Positions lo to mid - 1 are the left subtree and mid + 1 to hi the right one.
    10. Build the left subtree first and assign it to node.left. Its roots come right after this node in preorder, so the counter must serve it before the right subtree.
    11. Build the right subtree and assign it to node.right. By now the left subtree has used all of its roots, so the counter points at the right subtree's root.
    12. Return the node.

    The solution in Scala

    class Solution {
    val inorderIndex = scala.collection.mutable.HashMap[Int, Int]()
    var preIndex = 0

    def build(preorder: Array[Int], lo: Int, hi: Int): TreeNode = {
        if (lo > hi) {
            return null
        }
        val value = preorder(preIndex)
        preIndex += 1
        val node = new TreeNode(value)
        val mid = inorderIndex(value)
        node.left = build(preorder, lo, mid - 1)
        node.right = build(preorder, mid + 1, hi)
        return node
    }

    def buildTree(preorder: Array[Int], inorder: Array[Int]): TreeNode = {
        for (i <- inorder.indices) {
            inorderIndex(inorder(i)) = i
        }
        return build(preorder, 0, inorder.length - 1)
    }
}

    Following the example, here is each call of build as it runs on preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7], with the range it receives and, for a real node, the value it takes and that value's index in inorder:

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

    The values 3, 9, 20, 15 and 7 are taken in exactly the order of preorder, which is why a single counter is enough.

    Scala details worth knowing:

    • Updating a map. inorderIndex(inorder(i)) = i is shorthand for calling update on the map: it stores the value under that key. Reading inorderIndex(value) throws a NoSuchElementException for a missing key, which can't happen here because every value of preorder is also in inorder. For a key that might be missing, get returns an Option.
    • val and var on fields. inorderIndex is a val: the field always refers to the same map, but the map itself is mutable and grows. preIndex is a var because the number changes.
    • Arrays are indexed with parentheses: preorder(preIndex), not square brackets. inorder.indices is the range 0 until inorder.length.
    • Fields keep their state. preIndex and inorderIndex live as long as the Solution object. A fresh object per tree works as shown above. Calling buildTree a second time on the same object continues from the old preIndex and runs past the end of preorder, which throws an ArrayIndexOutOfBoundsException.

    Complexity

    Time: O(n). Filling the map visits each index once. build is called once for each of the n nodes plus once for each empty child, which is at most n + 1 calls, and each call does constant work because the map lookup is constant time. Searching inorder from scratch at every node would cost O(n) per node and O(n²) in total for a tall tree.

    Space: O(n). The map holds one entry per value, and the recursion goes as deep as the tree, at most n levels (the lesson limits it to 400).

    Edge cases and common mistakes

    • One value. preorder = [-1], inorder = [-1] gives [-1]: both ranges below the root are empty.
    • Building the right subtree first. The counter would hand the left subtree's roots to the right side. The left call must come first.
    • Same preorder, different inorder. With preorder = [1,2,3], inorder = [3,2,1] gives [1,2,null,3], a line going left. inorder = [1,2,3] gives [1,null,2,null,3], a line going right. inorder = [2,1,3] gives a full tree, [1,2,3]. Inorder is what decides the shape.
    • Wrong range bounds. The root itself is at mid, so the left range ends at mid - 1 and the right range starts at mid + 1. Using mid in either one puts the root into its own subtree and the recursion never ends.
    • Passing the preorder range down. Only inorder needs a range. Preorder is read through the shared counter, so there's no need to compute where its parts start and end.

    Testing

    Results from running the solution, printed level by level:

    preorderinorderResult
    [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]
    [1,2,3][2,1,3][1,2,3]
    [1,2,3,4][3,2,4,1][1,2,null,3,4]
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free