105. Construct Binary Tree from Preorder and Inorder Traversal#

Difficulty: Medium

Link to Problem: To see the Construct Binary Tree from Preorder and Inorder Traversal problem on LeetCode, click here!

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.

Constraints:

  • 1 <= preorder.length <= 3000

  • inorder.length == preorder.length

  • -3000 <= preorder[i], inorder[i] <= 3000

  • preorder and inorder consist of unique values.

  • Each value of inorder also appears in preorder.

  • preorder is guaranteed to be the preorder traversal of the tree.

  • inorder is guaranteed to be the inorder traversal of the tree.

Solution:#

Here’s a Python function to solve this problem:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder, inorder):
    if not preorder:
        return None

    # The first element in the preorder traversal is the root of the current subtree
    root_val = preorder[0]
    root = TreeNode(root_val)

    # Find the index of the root value in the inorder traversal
    root_idx_inorder = inorder.index(root_val)

    # Recursively build left and right subtrees
    root.left = buildTree(preorder[1:1 + root_idx_inorder], inorder[:root_idx_inorder])
    root.right = buildTree(preorder[1 + root_idx_inorder:], inorder[root_idx_inorder + 1:])

    return root

Explanation:#

  1. class TreeNode:: This is a class definition for a binary tree node. It has three attributes:

    • val: The value of the node.

    • left: A reference to the left child node.

    • right: A reference to the right child node.

    This class is used to create instances of binary tree nodes, which will be used to build the binary tree.

  2. def buildTree(preorder, inorder):: This is the main function that constructs a binary tree from its preorder and inorder traversals.

    • preorder: A list representing the preorder traversal of the binary tree.

    • inorder: A list representing the inorder traversal of the binary tree.

  3. if not preorder: return None: This line checks if the preorder list is empty. If it is, it means there are no nodes to construct, so the function returns None.

  4. root_val = preorder[0]: The value of the root node is extracted from the first element of the preorder list.

  5. root = TreeNode(root_val): A new TreeNode object is created with the root_val as its value. This represents the root of the current subtree.

  6. root_idx_inorder = inorder.index(root_val): The index of the root_val in the inorder list is found. This index indicates the position of the root node in the inorder traversal.

  7. root.left: The left subtree is constructed recursively by calling the buildTree function with the appropriate sublists of preorder and inorder. The left subtree’s preorder and inorder traversals are the slices of preorder and inorder lists up to the root_idx_inorder.

  8. root.right: The right subtree is constructed recursively by calling the buildTree function with the appropriate sublists of preorder and inorder. The right subtree’s preorder and inorder traversals are the slices of preorder and inorder lists starting from root_idx_inorder + 1.

  9. Finally, the function returns the root of the subtree it just constructed.

The recursive approach used here divides the problem of constructing the entire binary tree into smaller subproblems, starting with the root node and then recursively building the left and right subtrees until the entire tree is constructed.

Helper Function#

Here is a helper function to represent the binary tree elements.

def treeToList(root):
    # Initialize an empty list to store the elements of the binary tree
    result = []
    
    # Initialize a queue for level-order traversal starting with the root
    queue = [root]

    while queue:
        # Pop the front node from the queue
        node = queue.pop(0)
        
        # If the node is not None (i.e., a valid node), add its value to the result list
        if node:
            result.append(node.val)
            
            # Add the left and right children of the node to the queue
            queue.append(node.left)
            queue.append(node.right)
        else:
            # If the node is None, add None to the result to represent an empty node
            result.append(None)

    # Remove any trailing None values from the result list
    while result and result[-1] is None:
        result.pop()

    # Return the resulting list representing the binary tree elements
    return result

Explanation:#

Let’s break down the treeToList helper function step by step:

  1. def treeToList(root):: This function takes the root of a binary tree as input and converts it into a list.

  2. result = []: Initialize an empty list called result to store the elements of the binary tree in list format.

  3. queue = [root]: Initialize a queue data structure for a level-order traversal, starting with the root node.

  4. while queue:: This starts a loop that continues until the queue is empty, indicating that all nodes have been processed.

  5. node = queue.pop(0): Dequeue the first node from the queue, effectively processing it.

  6. if node:: Check if the node is not None, which means it’s a valid node in the binary tree.

    a. result.append(node.val): If the node is valid, append its value (node.val) to the result list. This represents the value of the current node in the binary tree.

    b. queue.append(node.left): Enqueue the left child of the current node if it exists. This adds the left child to the queue for processing in the next iteration.

    c. queue.append(node.right): Enqueue the right child of the current node if it exists. This adds the right child to the queue for processing in the next iteration.

  7. else:: If the node is None, it represents an empty node in the binary tree.

    a. result.append(None): Append None to the result list to indicate an empty node.

  8. while result and result[-1] is None:: After the traversal is complete, there might be trailing None values in the result list. This loop removes any such trailing None values to ensure a clean representation of the tree’s elements.

  9. return result: Return the result list, which now contains the elements of the binary tree in a format where None represents empty nodes and the order of elements reflects a level-order traversal of the tree.

In summary, the treeToList function performs a level-order traversal of the binary tree using a queue, constructing a list where each element corresponds to a node’s value or represents an empty node with None. This list represents the binary tree’s elements in a structured format.

Test cases#

# Example 1: 

# Example usage:
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
result = buildTree(preorder, inorder)

print(treeToList(result))

[3, 9, 20, None, None, 15, 7]

# Example 2:

preorder = [-1]
inorder = [-1]
result = buildTree(preorder, inorder)

print(treeToList(result))

[-1]

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the buildTree function:

Time Complexity: The time complexity of the buildTree function can be analyzed in terms of the number of nodes in the binary tree. Let’s assume there are n nodes in the binary tree.

  1. Finding the root value in the preorder traversal takes O(1) time as it’s just extracting the first element from the list.

  2. Finding the index of the root value in the inorder traversal using inorder.index(root_val) takes O(n) time in the worst case because in the worst case, it might have to search through all n elements in the inorder list to find the index.

  3. The recursive calls to buildTree for the left and right subtrees are made once for each node in the tree. Therefore, the recursive calls have a combined time complexity of O(n) as they process each node once.

The total time complexity of the buildTree function is O(n) due to the recursive calls and finding the root’s index in the inorder list.

Space Complexity: The space complexity is determined by the space used by the function’s call stack during recursion and any additional data structures used.

  1. The space used by the function call stack during recursion depends on the height of the binary tree. In the worst case, where the tree is highly unbalanced (e.g., a skewed tree), the space complexity for the call stack is O(n) as it can go as deep as the number of nodes in the tree.

  2. Additionally, the function creates TreeNode objects for each node in the binary tree. Therefore, the space complexity for these objects is also O(n).

Overall, the space complexity of the buildTree function is O(n) due to the space used by the call stack and the TreeNode objects.

In summary, the time complexity of buildTree is O(n), and the space complexity is O(n), where ‘n’ is the number of nodes in the binary tree.

Challenging Exercises:#

  1. Construct Binary Tree from Postorder and Inorder Traversal: Modify the problem to construct a binary tree from its postorder and inorder traversals. Implement a function similar to buildTree but for postorder and inorder traversals.

  2. Reconstruct Binary Tree with Duplicate Values: Extend the problem to handle binary trees with duplicate values. Ensure that your solution correctly handles scenarios where there are duplicate values in the preorder and inorder traversals.