Start learning free

LESSON 421 OF 540 · BINARY TREES

Build a Binary Tree from Preorder and Inorder in Kotlin: 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

    KOTLIN · BINARY TREES

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

    Problem overview

    Two integer arrays describe the same binary tree, and all values are different. preorder lists each node before its left subtree and its right subtree. inorder lists the left subtree, then the node, then the right subtree. The function buildTree(preorder, inorder) must rebuild the tree and return its root as a TreeNode?.

    The lesson provides TreeNode: a class with an Int property value and two nullable properties, left and right, both null at first.

    Example: preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7] give the tree [3,9,20,null,null,15,7]. The tests print a tree level by level, with null for missing children and the trailing nulls left out. Here 3 is the root, 9 is its left child, and 20 is its right child with the children 15 and 7.

    Approach

    Two facts do all the work:

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

    In the example, 3 is first in preorder. In inorder, 9 is left of 3 and 15, 20, 7 are right of it. So the left subtree holds one value, and the right subtree holds three. The same idea applies inside each part: the next unused value in preorder is the root of the next subtree, and its position in inorder splits that subtree's range in two.

    A direct version searches inorder for each root with a loop, which costs O(n) per node and O(n squared) overall in the worst case, such as a tree shaped like a line. Because all values are different, each value has exactly one position in inorder, so we can record every position once in a HashMap and answer each lookup in O(1). That brings the whole job to O(n).

    One more detail makes the recursion simple. Preorder visits a subtree's root first, then all of its left subtree, then all of its right subtree. If the recursion builds the left subtree before the right one, it uses the values of preorder strictly from left to right. A single counter that only moves forward is enough, and no ranges of preorder have to be passed around.

    Step by step

    1. Keep the positions. Make a HashMap<Int, Int> named inorderIndex as a property of the class, so the helper can read it as well.
    2. Keep the counter. Add var preIndex = 0, the position in preorder of the next root to use.
    3. Fill the map. In buildTree, loop over inorder.indices and store inorderIndex[inorder[i]] = i.
    4. Start the recursion. Return build(preorder, 0, inorder.size - 1). The pair 0 and inorder.size - 1 are the first and last positions of inorder: the whole tree.
    5. The helper build. It builds the subtree whose values fill inorder from lo to hi. If lo > hi, the range is empty, so return null: that is how the recursion ends below a leaf.
    6. Take the root. Read preorder[preIndex] into value, then move preIndex forward by one, and create TreeNode(value).
    7. Split the range. Look up mid = inorderIndex[value]!!. Positions lo to mid - 1 are the left subtree and mid + 1 to hi the right subtree.
    8. Build the left subtree first, then the right one, and attach them as node.left and node.right. The order is not a style choice: when the left call returns, it has used exactly the left subtree's roots, so preIndex points at the right subtree's root.
    9. Return node.

    The solution in Kotlin

    class Solution {
    val inorderIndex = HashMap<Int, Int>()
    var preIndex = 0

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

    fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
        for (i in inorder.indices) {
            inorderIndex[inorder[i]] = i
        }
        return build(preorder, 0, inorder.size - 1)
    }
}

    Kotlin details worth knowing

    • Properties are shared state. inorderIndex and preIndex belong to the Solution object, so every call of build sees the same map and the same counter. That is what lets the counter advance across the recursive calls. val means the property always holds the same map (which can still grow), while var lets preIndex change.
    • A fresh object per tree. Because preIndex is never reset, one Solution object is meant to build one tree. Calling buildTree a second time on the same object starts with the counter where the first call left it, so the second call reads the wrong values or runs off the end of preorder: building [1,2]/[2,1] twice with one object throws an ArrayIndexOutOfBoundsException the second time. Create a new Solution() for each tree, or set preIndex = 0 at the start of buildTree in code of your own.
    • !! on a map lookup. inorderIndex[value] has the type Int?, because a map returns null for a missing key. The compiler rejects val mid: Int = inorderIndex[value] with initializer type mismatch: expected 'Int', actual 'Int?'. The !! says the key is there, which is true for valid input. It throws a NullPointerException if it isn't, for example for a preorder that holds a value missing from inorder.
    • IntArray and indices. inorder.indices is the range 0..inorder.size - 1, so the loop needs no manual bounds. The array parameters are used as they come: nothing is copied or sliced.
    • Return type TreeNode?. build may return null for an empty range, so its type must be nullable, and so must node.left and node.right, which receive its result.

    Complexity

    • Time: O(n). Filling the map visits each position of inorder once. Then build creates exactly one node per value, and each call does O(1) work: one array read, one map lookup and two recursive calls. A call with an empty range does nothing but return, and there are n + 1 of those.
    • Space: O(n). The map stores n entries and the tree itself has n nodes. The recursion goes as deep as the tree is tall, up to n levels for a line, and the constraints keep it at 400.

    Edge cases and common mistakes

    • Building the right subtree first. With the counter approach, the order of the two recursive calls is fixed by preorder. Swap them and the values land in the wrong subtrees.
    • Off-by-one in the ranges. The left part is lo to mid - 1 and the right part is mid + 1 to hi: the root at mid belongs to neither.
    • One node. With [-1] and [-1], the root's range splits into two empty ranges and the tree is just [-1]. Negative values are fine because they are only stored and looked up.
    • A tree that is a line. The same preorder = [1,2,3] gives different trees for different inorder arrays: [3,2,1] gives [1,2,null,3] (only left children), and [1,2,3] gives [1,null,2,null,3] (only right children).
    • Repeated values. The method relies on all values being different. With duplicates, a value would have several positions and the map would keep only the last one.

    Testing

    These results come from running the solution with a new Solution object for each pair:

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