NUHMAN.com

Introduction

LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal asks you to construct a binary tree from its preorder and inorder traversal sequences. You are given two arrays representing the preorder and inorder traversal of a binary tree, and your task is to rebuild the tree.

This problem is commonly solved using a recursive approach by utilizing the properties of the preorder and inorder traversals.

Problem Statement

Given two integer arrays preorder and inorder where:

• preorder is the preorder traversal of a binary tree.
• inorder is the inorder traversal of the same binary tree.

Return the root of the binary tree.

Example:

go

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

Output:
    [3,9,20,null,null,15,7]

Approach:

Recursive Approach

1. Preorder Traversal: The first element in the preorder list is the root of the tree.
2. Inorder Traversal: The inorder list contains elements left of the root node in the left subtree and elements to the right of the root node in the right subtree.
3. Recursive Subproblem: After determining the root, recursively build the left and right subtrees by dividing the preorder and inorder arrays based on the root.

Steps:

1. The first element of the preorder array is always the root of the tree.
2. Find the root in the inorder array to separate the left and right subtrees.
3. Recursively construct the left subtree using the appropriate segments of preorder and inorder arrays.
4. Recursively construct the right subtree using the appropriate segments of preorder and inorder arrays.

Go Implementation

Recursive Solution to Construct Binary Tree

go

package main

// TreeNode represents the structure of a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// buildTree constructs a binary tree from preorder and inorder traversals.
func buildTree(preorder []int, inorder []int) *TreeNode {
    // Create a map to store the index of each value in inorder array
    inorderMap := make(map[int]int)
    for i, val := range inorder {
        inorderMap[val] = i
    }

    // Start the recursive tree construction
    return build(preorder, inorderMap, 0, len(preorder)-1, 0)
}

// build is a helper function that recursively constructs the binary tree.
func build(preorder []int, inorderMap map[int]int, preorderStart, preorderEnd, inorderStart int) *TreeNode {
    // Base case: if there are no elements to construct the tree
    if preorderStart > preorderEnd {
        return nil
    }
    
    // The first element of preorder is the root
    rootVal := preorder[preorderStart]
    root := &TreeNode{Val: rootVal}

    // Find the root index in the inorder array
    rootIndex := inorderMap[rootVal]

    // Number of nodes in the left subtree
    leftSize := rootIndex - inorderStart

    // Recursively build the left and right subtrees
    root.Left = build(preorder, inorderMap, preorderStart+1, preorderStart+leftSize, inorderStart)
    root.Right = build(preorder, inorderMap, preorderStart+leftSize+1, preorderEnd, rootIndex+1)

    return root
}

Explanation:

1. TreeNode Structure:

• The TreeNode struct represents a node in the binary tree with a value (Val) and pointers to the left (Left) and right (Right) children.

1. buildTree Function:

• The buildTree function is the main function that takes the preorder and inorder arrays as inputs.
• It creates a map (inorderMap) to store the index of each element in the inorder array for fast lookup.
• The function then calls the helper function build to construct the tree recursively.

1. build Function:

• The build function is a recursive helper function that constructs the binary tree.
• It receives the preorder array, inorderMap, and the current ranges of the preorder and inorder arrays being considered.
• The base case returns nil if there are no nodes to process.
• The root of the tree is the first element in the current preorder range.
• The function calculates the index of the root in the inorder array using inorderMap.
• It then recursively constructs the left and right subtrees based on the calculated sizes of the left subtree.

1. Recursive Construction:

• The left subtree is constructed by using the next segment of the preorder array (after the root) and the appropriate segment of the inorder array (to the left of the root).
• The right subtree is constructed using the remainder of the preorder and inorder arrays (to the right of the root).

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

Where:

• n is the number of nodes in the binary tree.

Time Complexity:

• The function processes each node exactly once. For each node, we look up its index in the inorderMap, which is an O(1) operation.
• Therefore, the time complexity is O(n), where n is the number of nodes.

Space Complexity:

• The space complexity is dominated by the recursion stack and the inorderMap, both of which require O(n) space. The recursion stack depth is proportional to the height of the tree, which can be up to O(n) in the worst case for a skewed tree.

Edge Cases

1. Empty Tree:

• Input: preorder = [], inorder = []
• Output: nil
• Explanation: An empty tree has no nodes, so the tree is nil.

1. Single Node Tree:

• Input: preorder = [1], inorder = [1]
• Output: [1]
• Explanation: A tree with only one node has just the root.

1. Tree with Only Left Subtree:

• Input: preorder = [3, 2, 1], inorder = [1, 2, 3]
• Output: [3,2,1]
• Explanation: A tree with only a left child (no right children) will have its nodes in reverse order in the inorder array.

1. Tree with Only Right Subtree:

• Input: preorder = [1, 2, 3], inorder = [1, 2, 3]
• Output: [1,null,2,null,3]
• Explanation: A tree with only a right child will have the nodes in the same order in both the preorder and inorder arrays.

Conclusion

LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal is a classic problem that requires you to reconstruct a binary tree using two traversal sequences. By leveraging the properties of preorder and inorder traversals, we can use a recursive approach to efficiently rebuild the tree. This approach is optimal with a time complexity of O(n) and space complexity of O(n), where n is the number of nodes. This problem tests your understanding of tree traversal and recursive problem-solving techniques.