107. Binary Tree Level Order Traversal II

MediumTreeBreadth-First SearchBinary Tree
Leetcode Link

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.

Flowchart Walkthrough

Let's use the flowchart to determine the appropriate algorithm for solving Leetcode 107: Binary Tree Level Order Traversal II. You can view the decision-making process using the Flowchart. Here is how we progress through the flowchart for this problem:

Is it a graph?

  • Yes: A binary tree is a type of graph where each node has up to two children.

Is it a tree?

  • Yes: The structure given is specifically a binary tree.

Does this scenario utilize Depth-First Search (DFS)?

  • No: Although DFS could be used, the problem specifically asks for level order traversal from bottom to top, which aligns perfectly with Breadth-First Search (BFS) due to its nature of visiting nodes level by level.

Conclusion: The flowchart directs us to use BFS for this tree structure problem, where the traversal is specifically mentioned to be from bottom to top level. Thus, BFS is suitable for visiting each level of the tree systematically, and then the levels can be reversed to achieve the "bottom-up" order as required by the problem statement.

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

    3
   / \
  9  20
    /  \
   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

1from collections import deque
2
3# Definition of a binary tree node.
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10
11class Solution:
12    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
13        """
14        Perform a level order traversal of the tree from the bottom up.
15          
16        Args:
17        root (Optional[TreeNode]): The root of the binary tree.
18          
19        Returns:
20        List[List[int]]: A list of lists with the values of the nodes at each level
21                         from bottom to top.
22        """
23        # The final answer list.
24        levels_reversed = []
25
26        # Return an empty list if the root is None.
27        if not root:
28            return levels_reversed
29
30        # Initialize a queue with the root for level order traversal.
31        queue = deque([root])
32
33        # Iterate while there are nodes in the queue.
34        while queue:
35            # Placeholder for values at the current level.
36            level_values = []
37
38            # Iterate over the nodes at the current level.
39            for _ in range(len(queue)):
40                current_node = queue.popleft()  # Get the next node from the queue.
41                level_values.append(current_node.val)  # Add its value to the level list.
42              
43                # If there are left/right children, add them to the queue for the next level.
44                if current_node.left:
45                    queue.append(current_node.left)
46                if current_node.right:
47                    queue.append(current_node.right)
48
49            # Append the current level's values to the beginning of the list.
50            levels_reversed.append(level_values)
51
52        # Return the level order values in reverse (i.e., from bottom to top).
53        return levels_reversed[::-1]
54
1class Solution {
2    public List<List<Integer>> levelOrderBottom(TreeNode root) {
3        // Initialize a linked list to store the result. We use LinkedList for efficient insertions at the beginning.
4        LinkedList<List<Integer>> result = new LinkedList<>();
5      
6        // If the root is null, return the empty result list.
7        if (root == null) {
8            return result;
9        }
10      
11        // We use a queue to facilitate level order traversal. Deque interface provides the ability to add/remove elements from both ends.
12        Deque<TreeNode> queue = new LinkedList<>();
13      
14        // Offer the root node to the end of the queue as a starting point for the level order traversal.
15        queue.offerLast(root);
16      
17        // Loop as long as there are nodes to process in the queue.
18        while (!queue.isEmpty()) {
19            // A temporary list to hold nodes values at the current level.
20            List<Integer> currentLevel = new ArrayList<>();
21          
22            // Number of elements to process at the current level equals the current queue size.
23            for (int i = queue.size(); i > 0; --i) {
24                // Poll the node from the front of the queue.
25                TreeNode node = queue.pollFirst();
26              
27                // Add its value to the current level list.
28                currentLevel.add(node.val);
29              
30                // If the left child exists, offer it to the end of the queue.
31                if (node.left != null) {
32                    queue.offerLast(node.left);
33                }
34              
35                // If the right child exists, offer it to the end of the queue.
36                if (node.right != null) {
37                    queue.offerLast(node.right);
38                }
39            }
40          
41            // At the end of each level, add the current level list to the front of the result list.
42            result.addFirst(currentLevel);
43        }
44      
45        // Return the resulting list of lists, which will be in bottom-up level order.
46        return result;
47    }
48}
49
1#include <vector>
2#include <queue>
3#include <algorithm>
4
5// Definition for a binary tree node.
6struct TreeNode {
7    int val;
8    TreeNode *left;
9    TreeNode *right;
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    // Function to perform a level-order traversal (bottom-up) of the tree.
17    vector<vector<int>> levelOrderBottom(TreeNode* root) {
18        vector<vector<int>> result; // This will store the final level order traversal in reverse order.
19      
20        // If the root is nullptr, return the empty result vector.
21        if (!root) return result;
22      
23        // Initialize a queue to hold the nodes of the tree.
24        queue<TreeNode*> nodesQueue;
25        nodesQueue.push(root);
26      
27        // Perform level-order traversal.
28        while (!nodesQueue.empty()) {
29            int levelSize = nodesQueue.size(); // Number of nodes at the current level.
30            vector<int> currentLevel; // This will store node values at the current level.
31          
32            // Iterate over all nodes at the current level.
33            for (int i = 0; i < levelSize; ++i) {
34                TreeNode* currentNode = nodesQueue.front(); // Get the next node from the queue.
35                nodesQueue.pop(); // Remove the node from the queue.
36              
37                currentLevel.push_back(currentNode->val); // Add the node's value to the current level's vector.
38              
39                // If the current node has a left child, add it to the queue for the next level.
40                if (currentNode->left) nodesQueue.push(currentNode->left);
41              
42                // If the current node has a right child, add it to the queue for the next level.
43                if (currentNode->right) nodesQueue.push(currentNode->right);
44            }
45          
46            // After finishing the current level, add it to the result vector.
47            result.push_back(currentLevel);
48        }
49      
50        // Since we want to return the result in reverse order, we reverse the entire result vector.
51        std::reverse(result.begin(), result.end());
52      
53        return result; // Return the final reversed level-order traversal.
54    }
55};
56
1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14/**
15 * Performs a level order traversal from bottom to top on a binary tree.
16 *
17 * @param {TreeNode | null} root - The root node of the binary tree.
18 * @return {number[][]} - A list of node values for each level, starting from the bottom level.
19 */
20const levelOrderBottom = (root: TreeNode | null): number[][] => {
21    const result: number[][] = [];
22    if (!root) return result;
23
24    // Queue to manage the tree nodes at each level
25    const queue: TreeNode[] = [root];
26
27    while (queue.length) {
28        const currentLevel: number[] = [];
29
30        // Loop through nodes at current level
31        for (let i = queue.length; i > 0; --i) {
32            const currentNode: TreeNode = queue.shift()!;  // the '!' asserts that we will not get null here
33            currentLevel.push(currentNode.val);
34
35            // Add child nodes to the queue for the next level
36            if (currentNode.left) queue.push(currentNode.left);
37            if (currentNode.right) queue.push(currentNode.right);
38        }
39
40        // Since we are dealing with bottom-up order, we prepend the current level to the result array
41        result.unshift(currentLevel);
42    }
43  
44    return result;
45};
46

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More