Taro Logo

Binary Tree Level Order Traversal II

Medium
Meta logo
Meta
1 view
Topics:
Trees

Question

Given the root of a binary tree, write a function to return the bottom-up level order traversal of its nodes' values.

In other words, the traversal should proceed level by level from the leaf nodes up to the root node. For each level, the nodes should be traversed from left to right.

Example 1:

Suppose you have the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

The expected output would be:

[[15, 7], [9, 20], [3]]

Example 2:

Consider a binary tree with only the root node:

  1

The expected output would be:

[[1]]

Example 3:

Now, suppose the binary tree is empty:

  None

The expected output would be:

[]

Clarifications/Constraints:

  • What should be returned if the input tree is None?
  • What is the range of values for the node values?
  • Can we assume that the input will always be a valid binary tree?

Solution


Bottom-Up Level Order Traversal of a Binary Tree

Problem Description

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

Naive Approach

A straightforward approach is to perform a standard level order traversal (breadth-first search) and then reverse the resulting list of lists. This involves:

  1. Performing a level order traversal using a queue.
  2. Storing the nodes' values for each level in a list.
  3. Reversing the order of the levels to obtain the bottom-up traversal.

Code (Python)

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrderBottom(root):
    if not root:
        return []

    queue = deque([root])
    levels = []

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        levels.append(current_level)

    return levels[::-1]  # Reversing the levels list

Big O Analysis

  • Time Complexity: O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the level order traversal.
  • Space Complexity: O(N), where N is the number of nodes in the binary tree. In the worst case, the queue can hold all nodes at the widest level, and the levels list can store all nodes.

Optimal Approach

An optimal approach avoids the explicit reversal step by inserting each level's nodes at the beginning of the result list. This maintains the bottom-up order as we traverse.

  1. Perform a level order traversal using a queue.
  2. For each level, insert the list of node values at the beginning of the result list.

Code (Python)

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrderBottomOptimal(root):
    if not root:
        return []

    queue = deque([root])
    levels = []

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        levels.insert(0, current_level)  # Insert at the beginning

    return levels

Big O Analysis

  • Time Complexity: O(N), where N is the number of nodes in the binary tree. We still visit each node once.
  • Space Complexity: O(N), where N is the number of nodes in the binary tree. The queue can hold up to the width of the tree, and the levels list stores all node values.

Edge Cases

  • Empty Tree: If the root is None, return an empty list.
  • Single Node Tree: If the tree contains only the root node, return a list containing a list with the root's value.

Summary

The optimal approach provides a cleaner solution by directly building the bottom-up level order traversal without a separate reversal step. Both approaches maintain O(N) time and space complexity, but the optimal approach is slightly more efficient due to avoiding the extra reversal operation.