Reverse Odd Levels of the Hotel

TIP102 Unit 9 Session 1 (Click for link to problem statements)
TIP103 Unit 10 Session 1 (Click for link to problem statements)

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-25 mins
🛠️ Topics: Binary Tree, Breadth First Search (BFS), Level Order Traversal

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

What shape is the hotel tree guaranteed to have?
- The tree is a perfect binary tree: every parent has exactly two children and all leaves are on the same level.
Which levels should be reversed?
- Only the odd levels, where the root is at level 0. So level 1, level 3, and so on have their room values reversed left to right.
Do we move the nodes themselves or just the values?
- Only the values stored in the nodes are swapped; the tree structure stays the same.

HAPPY CASE
Input: Perfect binary tree with level order values [2, 3, 5, 8, 13, 21, 34]
Output: Tree with level order values [2, 5, 3, 8, 13, 21, 34]
Explanation: Level 1 holds [3, 5], which reverses to [5, 3]. Level 2 is even, so it is unchanged.

Input: Perfect binary tree with level order values [7, 13, 11]
Output: Tree with level order values [7, 11, 13]
Explanation: Level 1 holds [13, 11], which reverses to [11, 13].

EDGE CASE
Input: Tree with a single room [5]
Output: Tree with a single room [5]
Explanation: There are no odd levels, so nothing changes.

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.

For problems that operate on whole levels of a binary tree, we can consider the following approaches:

Breadth First Search (BFS): A level order traversal visits the tree one level at a time, which makes it natural to reverse the values of an entire level in place.
Two Pointers: Within a level, swap values from both ends toward the middle to reverse the level.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the tree level by level with a queue. Collect each level’s nodes into a list, and on odd levels swap the stored values from the outside in.

1) If the root is None, return None.
2) Initialize a queue with the root and set the level counter to 0.
3) While the queue is not empty:
   a) Pop every node on the current level into a list.
   b) If the current level is odd, use two pointers (both ends of the list)
      to swap node values until the pointers meet.
   c) Enqueue the children of each node in the list.
   d) Increment the level counter.
4) Return the root.

⚠️ Common Mistakes

Reversing the even levels instead of the odd ones because of confusion about whether the root is level 0 or level 1.
Trying to rewire the child pointers instead of swapping the values, which is much harder to get right and unnecessary here.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

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

def reverse_odd_levels(root):
    if root is None:
        return None

    queue = deque([root])
    level = 0

    while queue:
        # Pop every node on the current level into a list for O(1) indexing
        current_level = []
        for _ in range(len(queue)):
            current_level.append(queue.popleft())

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

        # Enqueue the next level's children
        for node in current_level:
            if node.left:
                queue.append(node.left)
                queue.append(node.right)

        level += 1

    return root

Note: because the tree is perfect, a node either has both children or none, so checking node.left alone is enough before enqueueing both children.

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

Trace through the code with the tree [2, 3, 5, 8, 13, 21, 34]:
- Level 0 holds [2]; it is even, so nothing is swapped and its children [3, 5] are enqueued.
- Level 1 holds [3, 5]; it is odd, so the two values are swapped to [5, 3], then the children [8, 13, 21, 34] are enqueued.
- Level 2 holds [8, 13, 21, 34]; it is even and its nodes are leaves, so the traversal ends.
- The final level order is [2, 5, 3, 8, 13, 21, 34].

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the tree.

Time Complexity: O(N) because each node is enqueued and dequeued exactly once, and each value participates in at most one swap per level.
Space Complexity: O(N) because the queue and the per-level list hold an entire level at a time, and the widest level of a perfect binary tree contains about half of the nodes.