107. Binary Tree Level Order Traversal II

Problem Description

The LeetCode problem you're referring to asks for a bottom-up level order traversal of a binary tree. This means we should traverse the tree by levels, starting from the root, but instead of collecting the values from top to bottom, we need to return them from bottom to top. To visualize this, consider a tree with multiple levels; we would typically traverse it starting from the topmost level (the root), then move down one level at a time until we reach the leaves. In this problem, though, we're asked to report the level values starting from the leaves and work our way up to the root.

Intuition

The intuition behind the solution is that we can use a queue to perform a standard level order traversal from the root to the leaves. We would typically use a queue data structure to achieve this by enqueuing the root node, then continuously dequeuing a node while enqueueing its children until we have processed all levels of the tree.

However, to report the levels in reverse (from leaves to root), we can modify the standard level order traversal in the following way: as we traverse each level and collect values, we append the list of values to the beginning of our answer list (or alternatively, append to the end and then reverse the entire list at the end). By appending each new level to the front, the levels will be inverted when compared to a standard level order traversal, achieving the desired bottom-up effect.

To summarize, we're using a queue to manage the order of traversal and a list to collect the values. Each level's values are collected in a temporary list, which then gets added to our answer list. After completing the traversal, if we appended each level to the end, we simply reverse our answer list to achieve bottom-up order; if we appended each level to the front, no further action is required.

Learn more about Tree, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution provided uses a breadth-first search (BFS) algorithm to traverse the binary tree by levels, starting from the root. The BFS algorithm is typically implemented with the help of a queue data structure to keep track of the nodes to visit.

Here's a breakdown of the implementation steps:

1. Initialize an empty list ans which will hold our level order values in reverse order (from bottom to top).
2. Check if the root is None. If it is, return an empty list as there are no levels to traverse.
3. Initialize a deque q and add the root node to it. A deque is used instead of a regular queue as it allows for efficient addition and removal of elements from both ends. This is important as we will be traversing the tree level by level, and at each level, we deque nodes and enqueue their children.
4. We then enter a while loop that will run as long as there are nodes left in the queue to process. Inside this loop:
   • A temporary list t is initialized to store the values of the nodes at the current level.
   • We loop through the nodes in the current level, which is determined by the current length of the queue. For each node in this level:
     • The node is dequeued using q.popleft().
     • The value of the node is appended to the temporary list t.
     • If the node has a left child, it's enqueued.
     • Similarly, if the node has a right child, it's enqueued.
   • After collecting all values from the current level, the temporary list t is appended to the ans list. This ensures that ans contains list of values level by level.
5. Once the while loop completes (meaning all levels have been visited), the list ans is reversed using ans[::-1] since we've been appending each level's values at the end and we need the bottom-up order.
6. The reversed ans list is then returned. This list now represents the level order traversal of the binary tree from bottom to top.

Through the use of a deque and a list to collect our level values, coupled with the power of list comprehensions and the ease of reversing lists in Python, we've been able to construct a concise and effective solution to perform a bottom-up level order traversal of a binary tree.

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider a binary tree:

1    3
2   / \
3  9  20
4    /  \
5   15   7

We want to perform a bottom-up level order traversal of this binary tree. To do so, we follow the solution approach:

1. Initialization: Begin with an empty list ans to hold the level order values from bottom to top. The binary tree's root is 3, and since it's not None, we continue.

2. Set Up Queue: Initialize a deque q and add the root node (the value 3) to it.

3. Level Order Traversal:

   • Start the while loop since the queue is not empty.
   • For the first iteration, the queue contains just the root node [3].
   • Initialize a temporary list t for storing values of this level.

   First Level Iteration:

   • Dequeue the only element in the queue, which is 3.
   • Add 3 to the temporary list t = [3].
   • Enqueue its children (9 and 20) to the queue, so q = [9,20].
   • Append t to ans giving us ans = [[3]].

   Second Level Iteration:

   • Now, for each element at the current level (2 nodes, 9 and 20), dequeue and process:
     • Dequeue 9 from the queue (no children to enqueue), t becomes [9].
     • Dequeue 20, t becomes [9,20].
     • Enqueue 20's children (15 and 7) to the queue, so q = [15,7].
   • Append t to ans giving us ans = [[3], [9, 20]].

   Third Level Iteration:

   • Finally, process the last level with nodes 15 and 7.
     • Dequeue 15 (no children), t becomes [15].
     • Dequeue 7 (no children), t becomes [15, 7].
   • q is now empty, terminating the loop.
   • Append t to ans giving us ans = [[3], [9, 20], [15, 7]].

4. Reversing the Result: Since ans stores the levels from top to bottom, we reverse it to get the bottom-up order: [[15, 7], [9, 20], [3]].

5. Return Result: Our final result, representing the level order traversal from bottom to top, is [[15, 7], [9, 20], [3]].

This walkthrough demonstrates how the provided solution methodically performs a bottom-up level order traversal using BFS with a queue, a temporary list to collect each level's values, and then reverses the collected levels to achieve the desired result.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is O(N), where N is the number of nodes in the binary tree. This is because the algorithm traverses every node exactly once. With a queue, each node's value is processed and its children are added to the queue if they exist. This operation occurs for every node in the tree exactly once.

Space Complexity

The space complexity of the code is also O(N). In the worst-case scenario (when the tree is completely imbalanced), the queue could contain all nodes at the deepest level of the binary tree. In the case of a complete binary tree, this means the last level could have up to N/2 nodes, which is still considered O(N) in terms of space complexity. Additionally, the ans list will contain N elements as well since it stores the value of each node exactly once, contributing to the space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.