Problem of The Day: Reverse Odd Levels of Binary Tree

5 min read 1008 words

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.