Problem of The Day: Reverse Odd Levels of Binary Tree

Problem Statement

Intuition

The problem requires reversing the values of nodes at odd levels of a binary tree. A binary tree naturally lends itself to a level-order traversal using a queue. To solve the problem, the idea is to use a stack to temporarily store the values of nodes at odd levels during traversal, which allows for reversing their order when applied back to the tree.

Approach

1. Level-order Traversal: Perform a breadth-first search (BFS) using a queue to traverse the tree level by level.
2. Stack for Reversal: At each level:
   • If the level is odd, store the values of the nodes in a stack to reverse them.
   • Use an auxiliary queue to temporarily hold the nodes of the current level while applying the reversed values.
3. Update Values: For odd levels, pop values from the stack and assign them back to the corresponding nodes.
4. Proceed to Next Level: Enqueue the left and right children of the current level’s nodes for the next iteration.
5. Edge Cases: Ensure the algorithm handles cases such as trees with a single node or trees with no odd levels effectively.

Complexity

• Time Complexity: \(O(n)\), where \(n\) is the number of nodes in the binary tree. Each node is visited once, and the operations performed at each level are proportional to the number of nodes at that level.
• Space Complexity: \(O(w)\), where \(w\) is the maximum width of the tree. The space is used by the queue and stack, which hold nodes or values for one level at a time.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
from typing import Optional

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        queue = deque()
        queue.append(root)
        level = 0
        while queue:
            n = len(queue)
            stack = []
            curr_queue = deque()
            for i in range(n):
                node = queue.popleft()
                if node:
                    curr_queue.append(node)
                    if node.left:
                        stack.append(node.left.val)
                    if node.right:
                        stack.append(node.right.val)

            while curr_queue:
                node = curr_queue.popleft()
                if level % 2 == 0 and stack:
                    node.left.val = stack.pop()
                    node.right.val = stack.pop()
                queue.append(node.left)
                queue.append(node.right)

            level += 1
        return root

Editorial

Approach 1: Depth-First Search

class Solution:
    def reverseOddLevels(self, root) -> TreeNode:
        self.__traverse_DFS(root.left, root.right, 0)
        return root

    def __traverse_DFS(self, left_child, right_child, level):
        if left_child is None or right_child is None:
            return
        # If the current level is odd, swap the values of the children.
        if level % 2 == 0:
            temp = left_child.val
            left_child.val = right_child.val
            right_child.val = temp

        self.__traverse_DFS(left_child.left, right_child.right, level + 1)
        self.__traverse_DFS(left_child.right, right_child.left, level + 1)

Approach 2: Breadth-First Search

class Solution:
    def reverseOddLevels(self, root):
        if not root:
            return None  # Return None if the tree is empty.

        queue = [root]  # Start BFS with the root node.
        level = 0

        while queue:
            size = len(queue)
            current_level_nodes = []

            # Process all nodes at the current level.
            for _ in range(size):
                node = queue.pop(0)
                current_level_nodes.append(node)

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

            # Reverse node values if the current level is odd.
            if level % 2 == 1:
                left, right = 0, len(current_level_nodes) - 1
                while left < right:
                    tmp = current_level_nodes[left].val
                    current_level_nodes[left].val = current_level_nodes[
                        right
                    ].val
                    current_level_nodes[right].val = tmp
                    left += 1
                    right -= 1

            level += 1

        return root  # Return the modified tree root.