Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal

Problem

Leetcode 105 - Construct Binary Tree from Preorder and Inorder Traversal

Example:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Approach

We can use preorder traversal array for creating Binary Tree, and we can use inorder to check if we need to go right. For example with preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7], we know that our left most node is going to be 9. and our left most of right subtree is going to be 15.

Here is the Python code for the solution:

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        preidx, inidx = 0, 0
        def dfs(limit):
            nonlocal preidx, inidx
            if preidx >= len(preorder):
                return None
            if inorder[inidx] == limit:
                inidx += 1
                return None

            root = TreeNode(preorder[preidx])
            preidx += 1
            root.left = dfs(root.val)
            root.right = dfs(limit)
            return root

        return dfs(float('inf'))

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$