Construct Binary Tree From Preorder And Inorder Traversal - Leetcode Solution

Problem Statement: Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

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

Output: 3 /
9 20 /
15 7

Solution: The strategy here is to use the first element of the preorder list to construct the root of the binary tree. Then, we use the root value to divide the inorder list into left and right subtrees. We then recursively construct the left and right subtrees using the remaining elements in the preorder list.

Steps:

1. Define the recursive function constructTree(preorder, inorder, in_start, in_end) that returns a constructed binary tree in that subtree in inorder from in_start to in_end.

2. First, check if the list is empty.

3. Define the root of the tree as the first element in the preorder list.

4. Find the position of the root value in the inorder list, which will help in dividing the inorder list into left and right subtrees.

5. Calculate the length of the left subtree using the position of the root value in the inorder list.

6. Construct the left subtree by recursively calling the constructTree() function with the preorder and inorder lists corresponding to the left subtree.

7. Construct the right subtree by recursively calling the constructTree() function with the preorder and inorder lists corresponding to the right subtree.

8. Return the root of the constructed binary tree.

Code:

class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: def constructTree(preorder, inorder, in_start, in_end): if in_start > in_end: return None

        root_val = preorder.pop(0)
        root = TreeNode(root_val)

        root_index_inorder = inorder.index(root_val)
        length_left_subtree = root_index_inorder - in_start

        root.left = constructTree(preorder, inorder, in_start, root_index_inorder - 1)
        root.right = constructTree(preorder, inorder, root_index_inorder + 1, in_end)

        return root

    return constructTree(preorder, inorder, 0, len(inorder)-1)

Time Complexity: O(n^2) In the worst case, the function runs O(n) times, and each time it searches for the root value in the inorder list which takes O(n).

Space Complexity: O(n) In the worst case, the function uses O(n) space to store the binary tree.

1