LeetCode #105: Construct Binary Tree from Preorder and Inorder Traversal

LeetCode Solutions

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

Given the preorder and inorder traversal of a binary tree, the goal is to construct the binary tree.

Algorithm:

  1. If either the preorder or inorder traversal is empty, return None.
  2. Create a new node with the value of the first element in the preorder traversal.
  3. Find the index of the root node value in the inorder traversal. This splits the inorder traversal into left and right subtrees.
  4. Recursively build the left subtree by calling the buildTree function with the appropriate slices of the preorder and inorder traversals.
  5. Recursively build the right subtree by calling the buildTree function with the appropriate slices of the preorder and inorder traversals.
  6. Assign the left and right subtrees to the left and right attributes of the root node, respectively.
  7. Return the root node.
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1: mid+1], inorder[:mid])
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
        return root

We start by checking if either the preorder or inorder traversal is empty. If so, we return None. We then create a new node with the value of the first element in the preorder traversal. We find the index of the root node value in the inorder traversal, which splits the inorder traversal into left and right subtrees. We then recursively build the left subtree by calling the buildTree function with the appropriate slices of the preorder and inorder traversals. Similarly, we recursively build the right subtree by calling the buildTree function with the appropriate slices of the preorder and inorder traversals. Finally, we assign the left and right subtrees to the left and right attributes of the root node, respectively, and return the root node.

Time and Space Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree, since we visit each node only once. The space complexity of this solution is also O(n), since the maximum space used by the recursion stack is n. Therefore, this solution is both time and space-efficient.