NUHMAN.com

Introduction

LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal asks you to reconstruct a binary tree from its inorder and postorder traversal sequences. The inorder and postorder sequences are given, and you need to return the root of the binary tree.

This problem can be solved using a recursive approach, leveraging the properties of the inorder and postorder traversals.

Problem Statement

Given two integer arrays inorder and postorder where:

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

Return the root of the binary tree.

Example:

go

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

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

Approach:

Recursive Approach

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

Steps:

1. The last element of the postorder array is 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 postorder and inorder arrays.
4. Recursively construct the right subtree using the appropriate segments of postorder 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 inorder and postorder traversals.
func buildTree(inorder []int, postorder []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(inorder, postorder, inorderMap, 0, len(inorder)-1, 0, len(postorder)-1)
}

// build is a helper function that recursively constructs the binary tree.
func build(inorder []int, postorder []int, inorderMap map[int]int, inorderStart, inorderEnd, postorderStart, postorderEnd int) *TreeNode {
    // Base case: if there are no elements to construct the tree
    if inorderStart > inorderEnd || postorderStart > postorderEnd {
        return nil
    }

    // The last element of postorder is the root
    rootVal := postorder[postorderEnd]
    root := &TreeNode{Val: rootVal}

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

    // Number of nodes in the right subtree
    rightSize := inorderEnd - rootIndex

    // Recursively build the right and left subtrees
    root.Right = build(inorder, postorder, inorderMap, rootIndex+1, inorderEnd, postorderStart, postorderEnd-rightSize-1)
    root.Left = build(inorder, postorder, inorderMap, inorderStart, rootIndex-1, postorderStart+rightSize, postorderEnd-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 inorder and postorder 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 recursively construct the tree.

1. build Function:

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

1. Recursive Construction:

• The right subtree is constructed by using the appropriate segment of the postorder array (excluding the root) and the segment of the inorder array to the right of the root.
• The left subtree is constructed by using the remaining part of the postorder array (after the right subtree) and the segment of the inorder array to the left 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: inorder = [], postorder = []
• Output: nil
• Explanation: An empty tree has no nodes, so the tree is nil.

1. Single Node Tree:

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

1. Tree with Only Left Subtree:

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

1. Tree with Only Right Subtree:

• Input: inorder = [1, 2, 3], postorder = [3, 2, 1]
• 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 postorder and inorder arrays.

Conclusion

LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal is a great problem to practice reconstructing a binary tree using two traversal sequences. By utilizing the properties of postorder and inorder traversals, we can recursively rebuild the tree. This problem tests your understanding of tree traversal and recursive problem-solving techniques. The solution is optimal with a time complexity of O(n) and space complexity of O(n), where n is the number of nodes in the tree.