NUHMAN.com

Introduction

LeetCode 107: Binary Tree Level Order Traversal II asks you to return the level order traversal of a binary tree's nodes, but in reverse order. In other words, you need to return the bottom-up level order traversal of the binary tree.

This problem can be solved using a Breadth-First Search (BFS) approach, where we traverse the tree level by level, and then simply reverse the order of the result at the end.

Problem Statement

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

Example:

go

Input:
    root = [3,9,20,null,null,15,7]
Output:
    [[15,7],[9,20],[3]]

Approach:

Breadth-First Search (BFS) Approach

To solve this problem, we can use a Breadth-First Search (BFS) strategy. Here's how it works:

1. Level Order Traversal: BFS inherently processes nodes level by level. We can use a queue to help us achieve this. We will enqueue nodes and then dequeue them, processing each level sequentially.
2. Collect Nodes by Level: For each level, we will collect the values of the nodes and store them in a list.
3. Reverse the Result: After processing all the levels, we simply reverse the list of levels to get the bottom-up traversal.

Steps:

1. Initialize a queue with the root node.
2. Perform BFS by processing each level of the tree:

• For each level, collect the node values.
• Enqueue the child nodes (left and right) for the next level.

1. After processing all the levels, reverse the list of level values.
2. Return the reversed list.

Go Implementation

Breadth-First Search (BFS) Solution to Bottom-Up Level Order Traversal

go

package main

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

// levelOrderBottom performs a bottom-up level order traversal of the binary tree.
func levelOrderBottom(root *TreeNode) [][]int {
    // If the root is nil, return an empty slice.
    if root == nil {
        return [][]int{}
    }

    // Queue for BFS.
    queue := []*TreeNode{root}
    result := [][]int{}

    // Perform BFS.
    for len(queue) > 0 {
        levelSize := len(queue)
        levelValues := []int{}

        // Process all nodes at the current level.
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            // Add the node's value to the levelValues list.
            levelValues = append(levelValues, node.Val)

            // Enqueue the left and right children if they exist.
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        // Add the current level to the result.
        result = append([][]int{levelValues}, result...)
    }

    return result
}

Explanation:

1. TreeNode Structure:

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

1. levelOrderBottom Function:

• This function takes the root of the tree as input and returns a 2D slice containing the bottom-up level order traversal of the tree.
• If the root is nil, the function immediately returns an empty slice.

1. Queue for BFS:

• A queue (queue) is used to perform a level-order traversal. Initially, the queue contains the root of the tree.

1. BFS Traversal:

• For each level of the tree, the function processes all nodes at that level:
• It records the values of the nodes in the levelValues slice.
• It enqueues the left and right children of the current nodes (if they exist) for the next level.

1. Reverse the Result:

• Instead of appending the level values to the result as usual, we prepend (append([][]int{levelValues}, result...)) the level values to the result. This ensures that the bottom-most levels appear first in the final result.

1. Return the Result:

• Finally, the function returns the reversed 2D slice of level values, which represents the bottom-up level order traversal.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

Where:

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

Time Complexity:

• The algorithm processes each node once, so the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity:

• The space complexity is O(n) because we store all the nodes in the queue and the result. In the worst case, the queue may hold all the nodes at the bottom-most level, which is the largest level in the tree.

Edge Cases

1. Empty Tree:

• Input: root = nil
• Output: []
• Explanation: An empty tree should return an empty list.

1. Single Node Tree:

• Input: root = [1]
• Output: [[1]]
• Explanation: A tree with just one node has only one level, which is returned as the result.

1. Complete Binary Tree:

• Input: root = [1, 2, 3, 4, 5, 6, 7]
• Output: [[4,5,6,7],[2,3],[1]]
• Explanation: A complete binary tree has all levels fully populated, and the result will contain the node values in reverse level order.

1. Unbalanced Tree (All Left Children):

• Input: root = [1, 2, 3, 4]
• Output: [[4],[3],[2],[1]]
• Explanation: An unbalanced tree with only left children will have its levels arranged from leaf to root in reverse order.

Conclusion

LeetCode 107: Binary Tree Level Order Traversal II is a classic tree traversal problem where we need to return the level order traversal of a binary tree in reverse. By using Breadth-First Search (BFS), we process the tree level by level and then reverse the result to achieve the required bottom-up order. The solution is efficient with a time complexity of O(n) and a space complexity of O(n), where n is the number of nodes in the binary tree. This problem tests your understanding of tree traversal, BFS, and managing results in a reversed order.