Friedrich Ewald My Personal Website

Leetcode: Reconstruct binary tree

Given two lists of a preorder and inorder, create a tree and return the root node.

preorder: [3,9,20,15,7]
inorder:  [9,3,15,20,7]

Resulting tree:

    /   \
   9    20
       /  \
      15   7
The problem is not so obvious at first. If the preorder list would also contain null values for the places where the tree does not contain nodes, we could simply iterate over this list and reconstruct the tree from there. But since the null values are missing, we also need to take a look at the inorder list. We know about the preorder list that the traversal is as follows: NLR. This means that first the node is visited, then we go recursively to the left, and then recursively to the right. For inorder it is LNR: We go recursively to the left, then output the node, and finally go to the right. Because of those properties, we know that the root node is the first one in the preorder list. Since there is only one root node, we know that the next node will be in the next level. We don’t know, from looking at the preorder list, if the next child node is to the left or right. To figure this out, we need to look at the inorder list. If the node is to the left of our current element, know that it must be the immediate child to the left. We then determine the position of the node in the inorder list and pass it recursively to the same method. If it is to the right, we remove the left prefix from the preorder list, add it as a right node, and pass in the left and right lists to the recursive function. Finally, we return the root node.
from typing import List, Optional

# Definition for a binary tree node.
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
  def __repr__(self) -> str:
    """Convenience function for easy debugging"""
    return str(self.val)

class Solution:
  def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    if len(preorder) == 0:
      return None
    def inner(root, preorder, left, right):
      if len(preorder) == 0:

      # Determine if the element is left or right
      curr = preorder[0]
      idx = -1
      for i in range(len(left)):
        if left[i] == curr:
          idx = i
      # Next element is in the left part
      if idx > -1:
        root.left = TreeNode(curr)
        inner(root.left, preorder[1:], left[:idx], left[idx+1:])
      preorder = preorder[len(left):]
      idx = -1
      for i in range(len(right)):
        if right[i] == preorder[0]:
          idx = i
      if idx > -1:
        root.right = TreeNode(preorder[0])
        inner(root.right, preorder[1:], right[:idx], right[idx+1:])

    root = TreeNode(preorder[0])
    idx = -1
    for i in range(len(inorder)):
      if inorder[i] == preorder[0]:
        idx = i
    inner(root, preorder[1:], inorder[:idx], inorder[idx+1:])
    return root


if __name__ == '__main__':
  s = Solution().buildTree
  t1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
  # print(s([3,9,20,15,7,81], [9,3,15,20,81,7]), t1)
  print(s([3,1,2,4], [1,2,3,4]))
Runtime: 722 ms, faster than 5.01% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal. Memory Usage: 89.2 MB, less than 5.37% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.