Start learning free

LESSON 417 OF 536 · BINARY TREES

Construct Binary Tree from Preorder and Inorder in Python: O(n) with a Dict

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

STEP 1 OF 13
    Ctrl + Enter to check

    PYTHON · BINARY TREES

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

    Problem overview

    buildTree receives two lists, preorder and inorder, which are the traversals of the same binary tree. All values are different. The function must rebuild the tree and return its root. The lesson provides the TreeNode class: TreeNode(x) creates a node with val set to x and left and right set to None.

    With 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, and 20 has the children 15 and 7. Level by level, that is [3,9,20,null,null,15,7], the form the tests use to print a tree.

    Approach: preorder names the roots, inorder splits the sides

    Two facts do all the work:

    • In preorder, a subtree's root comes first, then its whole left subtree, then its whole right subtree. Reading preorder from left to right therefore gives the roots in the order the recursion needs them.
    • In inorder, the left subtree comes before the root and the right subtree after it. Once you know where the root sits in inorder, everything to its left is the left subtree and everything to its right is the right subtree.

    So the first value of preorder is the root, its position in inorder divides the remaining values into two groups, and each group is a smaller copy of the same problem. Every subtree occupies one unbroken stretch of inorder, so two indices, lo and hi, describe it.

    The only costly part is finding a value's position in inorder. Searching the list each time would cost O(n) per node and O(n²) overall. Since the values are distinct, a dict from each value to its index answers in constant time, which gives O(n) overall.

    Here is the recursion on the example. Each line is one call of build, with the stretch of inorder it covers:

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

    The root 3 sits at index 1 of inorder, so the left call covers indices 0 to 0 and the right call covers 2 to 4. The next root in preorder is 9, and it has no children: both of its calls get an empty range. Then the right call takes 20 from preorder, which sits at index 3 of inorder, and the process repeats.

    Step by step

    1. Create the lookup dict as self.inorderIndex, an attribute, so the helper written later can read it too.
    2. Loop over every index of inorder with range(len(inorder)).
    3. Store each value's index: self.inorderIndex[inorder[i]] = i. After the loop, any value's position is one lookup away.
    4. Start the preorder counter self.preIndex at 0. It points at the next root to use.
    5. Return the whole tree by calling self.build with preorder and the full range of inorder, from 0 to len(inorder) - 1.
    6. Declare the helper build(self, preorder, lo, hi). It returns the root of the subtree whose values fill inorder[lo..hi].
    7. Handle the empty range. If lo > hi, return None. Below a leaf, both ranges are empty, so this ends the recursion.
    8. Take the next root from preorder[self.preIndex] as value, then advance self.preIndex.
    9. Create the node with TreeNode(value).
    10. Find the split point: mid = self.inorderIndex[value].
    11. Build the left subtree from the range lo to mid - 1 and store it as node.left. It goes first because the left subtree's roots follow this node in preorder.
    12. Build the right subtree from mid + 1 to hi and store it as node.right. By then the left subtree has consumed all its roots, so the counter points at the right subtree's root.
    13. Return the node.

    The solution in Python

    class Solution:
    def build(self, preorder, lo, hi):
        if lo > hi:
            return None
        value = preorder[self.preIndex]
        self.preIndex += 1
        node = TreeNode(value)
        mid = self.inorderIndex[value]
        node.left = self.build(preorder, lo, mid - 1)
        node.right = self.build(preorder, mid + 1, hi)
        return node

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        self.inorderIndex = {}
        for i in range(len(inorder)):
            self.inorderIndex[inorder[i]] = i
        self.preIndex = 0
        return self.build(preorder, 0, len(inorder) - 1)

    Python details worth a closer look:

    • State on self. inorderIndex and preIndex are attributes of the Solution object, shared by every call of build. This is what lets the counter advance across the recursion without being passed along. A plain local variable would be a separate copy in each call.
    • The counter is reset every time. buildTree sets self.preIndex = 0 on each call, so one Solution object can build several trees in a row.
    • The order of the two recursive calls matters. The left call must come first, because it uses up the next roots in preorder. Swapping the two lines would hand the left subtree's roots to the right side.
    • Dict lookup. self.inorderIndex[value] raises KeyError for a missing key, but here the value always exists, since both lists hold the same values.

    Complexity

    Time: O(n). Filling the dict visits each value once. build creates each node exactly once, with one dict lookup and constant extra work, and returns for each empty range once, so about 2n + 1 calls in all.

    Space: O(n). The dict holds n entries and the tree itself has n nodes. The recursion goes as deep as the tree is tall, up to n levels in a one-sided tree; the lesson limits trees to 400 levels, within Python's default recursion limit of 1,000.

    Edge cases and common mistakes

    • A single value. preorder = [-1], inorder = [-1] gives a tree with just a root: [-1].
    • Lines of nodes. The same preorder = [1,2,3] gives [1,2,null,3] with inorder = [3,2,1] (every node has only a left child) and [1,null,2,null,3] with inorder = [1,2,3] (only right children).
    • Building the right subtree first. The counter then points at a left-subtree value and the tree comes out wrong.
    • Using the wrong bounds. The root at mid belongs to neither range, so the ranges are lo..mid - 1 and mid + 1..hi. Using mid in either one makes a range cover one value too many, so the counter runs ahead of the tree and the result is wrong.
    • Searching instead of looking up. inorder.index(value) works but costs O(n) per node, which makes the whole solution O(n²).

    Testing

    Each result below is the tree printed level by level:

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