Leetcode - Construct Binary Tree from Preorder and Inorder Traversal

Question

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.

This is atree question.

Idea(s)

• From the preorder tree, we can find the root (will always be the left most value)
• From the inorder tree, we can segment the left and right subtrees based on whether or not they come before or after the root node in the given array
• Select root from preorder tree (preorder[0]) then slice the inorder tree by inorder[:root_index] and inorder[[root_index+1:]]
• We want to recursively build the right and left subtrees removing the root and passing the required subtrees on each recursive call (the preorder subtree is 1:root_index+1 and root_index+1: for the left and right subtrees respectively)
• The base case if if there is no preorder or inorder array being passed
• Return the root
• The main trick here is to understand when passing the left subtree preorder array, the slice for the left subtree is 1:root_index+1
  • The +1 works because we are only concerned about the next root for the left subtree, if there are no other children, we would return a left subtree like [9] and indexing +1 would be out of bounds

Solution