The Blind 75 Leetcode Series: Construct Binary Tree from Preorder and Inorder Traversal

Today, we are working on 105. Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

We are given 2 lists, one as the preorder traversal result of a tree and another as the inorder traversal result of the same tree. From these lists, we want to figure out what this tree looks like.

Some questions to ask are:

  1. do we expect empty tree? (empty list)
  2. are the values in the lists unique?

If the interviewers tell us that the tree always contains some nodes and the values are all unique, then we can start.

If you are not familiar with the pre-order and in-order traversals, basically pre-order traversal records the value first, then go left, then go right. It repeats the process at every node until we go through the entire tree. In-order traversal goes left first until it can’t. Then it records the value. Then it goes right. Once it goes to the next node, the process repeats.

Knowing these properties, we can say a few things:

  1. the first value on the pre-order list is the root since pre-order traversal would record the value of the node first.
  2. Knowing the value of root, since all values are unique, we can find the index of the value in the in-order traversal. Once we do, every value on the left of the root value is on the left side of the tree, and every value on the right belongs to the right side of the tree.
  3. Now that we know the size of the tree on the left and on the right, we go back to pre-order list to slice the list. Since pre-order list would always have values from the left tree recorded first, if we know from the in-order list that there should be 3 nodes on the left tree, we can go ahead and slice the first 3 values from the pre-order list. These values should match. Try testing it.
  4. We now have two sets of pre-order and in-order combos. We can feed it into the same function again to recursively build this tree.

To put everything into code, it looks like

def buildTree(preorder, inorder):
if not preorder or not inorder:
return
root = TreeNode(preorder[0])
# find the index in the in-order list
idx = inorder.index(root.val)
# Slice the two lists into left-half and right-half. Knowing how to slide the lists is the key to this problem
left_preorder, right_preorder = preorder[1:idx+1], preorder[idx+1:]
left_inorder, right_inorder = inorder[:idx], inorder[idx+1:]
# recursively build the tree
root.left = self.buildTree(left_preorder, left_inorder)
root.right = self.buildTree(right_preorder, right_inorder)
return root

What’s the time complexity here? We are going over the list recursively due to that .index operation, which takes linear time. We end up with O(N²) overall.

def buildTree(preorder, inorder):
if not preorder or not inorder:
return
root = TreeNode(preorder[0])
# O(N)
idx = inorder.index(root.val)
left_preorder, right_preorder = preorder[1:idx+1], preorder[idx+1:]
left_inorder, right_inorder = inorder[:idx], inorder[idx+1:]
# recursion on O(N) makes it O(N^2)
root.left = self.buildTree(left_preorder, left_inorder)
root.right = self.buildTree(right_preorder, right_inorder)
return root

Can we do better? What if we can eliminate the .index? That seems like the biggest bottleneck. If we can reduce that to O(1), we can reduce the overall time complexity to O(N). What type of “tracking” can give us O(1) read time? That sounds like a job for dictionary (hash table).

We start with doing one iteration through the entire inorder list to get the positions of each number. Then we do the same operation, except this time we find the idx through hashtable.get(val) . But to do that, we can’t just slice the list since it’ll change the index position. We will need to find a way to correctly track the in-order list’s index.

Instead of slicing the in-order list, we can use 2 pointers, left and right, to determine how we want to slice it without actually slicing the list.

We still want to get the first element of the pre-order list, so we want to pass in the pre-order list as part of the recursive function inputs as well. Then we need to pass in the tracker to determine the position of the elements in in-order list.

So our recursive functions will take…

def recursive(left, right, preorder, inorder_index_map)

The logic is almost the same inside the recursive. We first take the first element of the pre-order list. Since we are not slicing the list this time, we want to pop it from the list. pop(0) is a O(N) operation, so we want to make sure to convert the pre-order list to a deque, so we can do a O(1) popleft().

We now just need to determine the correct value for left and right for each recursion.

Going back to the property of in-order list, we know that the left side of the target idx belongs to the left tree and the right side belongs to the right tree. So the left and right for the left tree is simply the same left and inorder_index_map[root_val] — 1, where inorder_index_map is the tracker we built and root_val is the value for the current node.

Similarly, for the right tree, we have the right being the same and left becomes inorder_index_map[root_val] + 1.

We can now put everything together.

from collections import dequedef recursive(left, right, preorder, inorder_index_map):
# if there are no elements to construct the tree
if left > right:
return
root_val = preorder.popleft()
root = TreeNode(root_val)
root.left = recursive(left, inorder_index_map[root_val] - 1, preorder, inorder_index_map)
root.right = recursive(inorder_index_map[root_val] + 1, right, preorder, inorder_index_map)
return rootdef buildTree(preorder, inorder]):
# so we can popleft with O(1)
preorder = deque(preorder)
# tracker for the value: idx of in-order list
inorder_index_map = {}
for index, value in enumerate(inorder):
inorder_index_map[value] = index
return recursive(0, len(preorder) - 1, preorder, inorder_index_map)

And now, because we eliminated the .index and we did not add any more O(N) operation, we are now only looking at O(N) overall time complexity.

def recursive(left, right, preorder, inorder_index_map):
if left > right: # O(1)
return
root_val = preorder.popleft() # O(1)
root = TreeNode(root_val) # O(1)

root.left = recursive(left, inorder_index_map[root_val] - 1, preorder, inorder_index_map)
root.right = recursive(inorder_index_map[root_val] + 1, right, preorder, inorder_index_map)
return rootdef buildTree(preorder, inorder]):
preorder = deque(preorder)
# building tracker: O(N)
inorder_index_map = {}
for index, value in enumerate(inorder):
inorder_index_map[value] = index
# overall recursive: O(N)
return recursive(0, len(preorder) - 1, preorder, inorder_index_map)

That’s it! Another problem down.

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jonathan Chao

Jonathan Chao

219 Followers

I am a software developer who has been in this industry for close to a decade. I share my experience to people who are or want to get into the industry