Leetcode 105 : Construct a tree from Preorder and Inorder Traversal

Reading Time : 7 minutes

Day 20/30.

I think this question is really interesting because not only is it able to test your knowledge about basic of a tree, but also if you can build those basics into something a little more complicated. Here is a short video explaining the question and the intuition behind the solution of the problem :

Like I said in my post about trees yesterday, trees are naturally defined recursively and you can use trends to solve most of the questions, including this one.

def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
       
        if not preorder or not inorder: # check for valid input 
            return None

        rootValue = preorder.pop(0) # root of tree = first value of preorder. We pop it because we will be working with the rest of the preorder now
        root = TreeNode(rootValue) # make the root of your resulting tree
        inorderIndex = inorder.index(rootValue) # find the value of the root in the inorder array 

        # the left of the root in inorder array forms the left child, which is itself a tree.
        root.left = self.buildTree(preorder, inorder[:inorderIndex])
        # repeat prev step for right     
        root.right = self.buildTree(preorder, inorder[inorderIndex+1:])

        return root

If you stick to the basics, even complicated sounding questions can be solved easily! The time and space complexity of this problem is O(N) if N is the number of nodes in the tree - you will have to traverse the entire arrays and build out each node.

We have one more Wednesday Walkthrough left so let me know in the comments below which leetcode question would you like to see!