Problem Description

You are given the root of a perfect binary tree. Your task is to reverse the node values at each odd level of the tree.

A perfect binary tree is a special type of binary tree where:

• Every parent node has exactly two children
• All leaf nodes are at the same depth/level

The level of a node is determined by counting the edges from the root to that node. The root is at level 0, its children are at level 1, and so on.

For odd-numbered levels (1, 3, 5, ...), you need to reverse the values of all nodes at that level horizontally. For example, if level 3 has nodes with values [2,1,3,4,7,11,29,18] from left to right, after reversing they should become [18,29,11,7,4,3,1,2].

The solution uses a level-order traversal (BFS) approach:

1. Use a queue to process nodes level by level
2. Track the current level with a counter i
3. When i is odd (checked using i & 1), swap the values of nodes at that level
   • Use two pointers from the start and end of the current level's nodes
   • Swap values moving the pointers toward each other
4. Add all children of the current level to the queue for the next iteration
5. Return the modified tree's root

The key insight is that we only need to swap the values of the nodes, not the actual node structures or their connections, which makes the problem simpler to solve.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree (specifically a perfect binary tree).

DFS

• Yes: We arrive at DFS as the suggested approach for tree problems.

Conclusion: The flowchart suggests using a DFS (Depth-First Search) approach for this tree problem.

How DFS Applies to This Problem

While the provided solution uses BFS (level-order traversal), DFS is equally valid and can solve this problem effectively:

1. DFS with Level Tracking: We can traverse the tree using DFS while keeping track of the current level. During traversal, we collect nodes at each odd level.

2. Two-Pass DFS Approach:

   • First pass: Collect all nodes at odd levels into lists
   • Second pass: Traverse again and update values using the reversed lists

3. Recursive DFS Solution: We can recursively traverse pairs of nodes at odd levels and swap their values directly:

   def dfs(left, right, level):
       if not left:
           return
       if level % 2 == 1:  # odd level
           left.val, right.val = right.val, left.val
       dfs(left.left, right.right, level + 1)
       dfs(left.right, right.left, level + 1)

The flowchart correctly identifies this as a tree problem where DFS is applicable, though the specific implementation can vary between DFS and BFS based on what's more convenient for level-wise operations.

Intuition

When we need to reverse values at specific levels of a tree, the key insight is that we need to process nodes level by level. This immediately suggests a level-order traversal pattern.

Think about what "reversing at a level" means - if we have nodes [A, B, C, D] at a level, we want their values to become [D, C, B, A]. The crucial observation is that we don't need to change the tree structure itself - we only need to swap the values stored in the nodes.

Since it's a perfect binary tree, every level (except leaves) has all nodes present, making our task simpler. At any odd level, we know exactly how many nodes exist: 2^level nodes.

For the swapping strategy, we can use a two-pointer approach:

• Collect all nodes at the current level
• If it's an odd level, place pointers at the start and end
• Swap values and move pointers toward each other until they meet

Why does this work better than DFS for this specific problem? While DFS can traverse the tree, BFS naturally groups nodes by level, which is exactly what we need. With BFS, we process all nodes at level 1, then all at level 2, and so on. This makes it trivial to identify when we're at an odd level (level % 2 == 1) and perform the reversal operation on exactly those nodes.

The elegance of the solution comes from recognizing that:

1. We need level-wise access to nodes
2. We only swap values, not node structures
3. A queue naturally maintains nodes in level order during BFS
4. The two-pointer technique efficiently reverses values in-place

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution uses Breadth-First Search (BFS) with a queue to traverse the tree level by level. Here's the step-by-step implementation:

1. Initialize the BFS Setup

• Create a queue q using deque([root]) to store nodes at each level
• Initialize a level counter i = 0 to track which level we're currently processing

2. Process Each Level While the queue is not empty:

• Check if current level i is odd using bitwise operation i & 1
  • This is equivalent to i % 2 == 1 but more efficient

3. Reverse Values at Odd Levels If we're at an odd level:

• Set two pointers: l = 0 (left) and r = len(q) - 1 (right)
• While l < r:
  • Swap values: q[l].val, q[r].val = q[r].val, q[l].val
  • Move pointers inward: l += 1, r -= 1
• This reverses all node values at the current level in-place

4. Add Next Level's Nodes Process all nodes at the current level:

• For each node in the current level (using range(len(q))):
  • Remove node from front: node = q.popleft()
  • If the node has children (guaranteed in perfect binary tree except for leaves):
    • Add left child: q.append(node.left)
    • Add right child: q.append(node.right)

5. Move to Next Level

• Increment level counter: i += 1
• Continue until all levels are processed

6. Return Result

• Return the original root with modified values

The algorithm maintains the tree structure intact while only modifying the values at odd levels. The time complexity is O(n) where n is the number of nodes, as we visit each node exactly once. The space complexity is O(w) where w is the maximum width of the tree (at most n/2 for a perfect binary tree).

Example Walkthrough

Let's walk through a small perfect binary tree example to illustrate the solution approach:

Initial Tree:

        1           (level 0)
       / \
      2   3         (level 1 - odd)
     / \ / \
    4  5 6  7       (level 2)

Step 1: Initialize

• Queue: [1]
• Level counter: i = 0

Step 2: Process Level 0 (Root)

• Current level is 0 (even), so no reversal needed
• Process node 1:
  • Remove 1 from queue
  • Add its children 2 and 3 to queue
• Queue after level 0: [2, 3]
• Increment level: i = 1

Step 3: Process Level 1 (Odd - Reverse!)

• Current level is 1 (odd), so we need to reverse
• Queue contains: [2, 3]
• Set pointers: l = 0, r = 1
• Swap values:
  • q[0].val (2) ↔ q[1].val (3)
  • Now nodes have values: [3, 2]
• Move pointers: l = 1, r = 0 (l >= r, stop)
• Process both nodes:
  • Remove node with value 3 (originally 2), add children 4, 5
  • Remove node with value 2 (originally 3), add children 6, 7
• Queue after level 1: [4, 5, 6, 7]
• Increment level: i = 2

Step 4: Process Level 2 (Even)

• Current level is 2 (even), so no reversal needed
• Process all 4 nodes:
  • They're leaf nodes, so no children to add
• Queue becomes empty
• Algorithm terminates

Final Tree:

        1           (level 0 - unchanged)
       / \
      3   2         (level 1 - reversed!)
     / \ / \
    4  5 6  7       (level 2 - unchanged)

The values at level 1 have been successfully reversed from [2, 3] to [3, 2], while maintaining the tree structure. Note that nodes 2 and 3 still have the same children as before - only their values were swapped, not their positions in the tree.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree.

The algorithm uses BFS (Breadth-First Search) to traverse the tree level by level. Each node is visited exactly once when it's dequeued from the queue. For odd levels, we perform value swaps which takes O(k) time where k is the number of nodes at that level. Since the total number of nodes across all levels is n, and each node is processed once (either just traversed or traversed + swapped), the overall time complexity is O(n).

Space Complexity: O(n) where n is the number of nodes in the binary tree.

The space complexity is determined by the queue q used for BFS traversal. In the worst case, the queue holds all nodes at the widest level of the tree. For a perfect binary tree (which this problem assumes based on the operation), the last level contains approximately n/2 nodes. Therefore, the maximum space used by the queue is O(n/2), which simplifies to O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Reverse After Processing the Current Level

A critical mistake is trying to reverse node values after already removing nodes from the queue for processing. This leads to attempting operations on an empty or partially processed queue.

Incorrect Implementation:

while queue:
    level_size = len(queue)
    # Process nodes first (WRONG ORDER!)
    for _ in range(level_size):
        node = queue.popleft()
        if node.left:
            queue.append(node.left)
            queue.append(node.right)
  
    # Try to reverse after nodes are already removed
    if level & 1:
        # Queue no longer contains current level nodes!
        left, right = 0, len(queue) - 1
        while left < right:
            queue[left].val, queue[right].val = queue[right].val, queue[left].val
            left += 1
            right -= 1

Why This Fails:

• After the for loop, the queue contains nodes from the NEXT level, not the current odd level
• You end up reversing the wrong level's values or getting index errors

Correct Approach:

• Always reverse BEFORE processing/removing nodes from the queue
• The queue should contain all nodes of the current level when reversing

2. Modifying Tree Structure Instead of Just Values

Another common mistake is trying to swap entire nodes or modify parent-child relationships instead of just swapping values.

Incorrect Approach:

# Trying to swap node references (WRONG!)
queue[left], queue[right] = queue[right], queue[left]

Why This Fails:

• This only swaps references in the queue, not in the actual tree
• Parent-child relationships remain unchanged
• The tree structure gets corrupted or remains unmodified

Correct Approach:

• Only swap the values: queue[left].val, queue[right].val = queue[right].val, queue[left].val
• Keep the tree structure intact

3. Using Wrong Level Indexing

Starting the level counter at 1 instead of 0, or incrementing at the wrong time.

Incorrect Implementation:

level = 1  # Starting at 1 (WRONG!)
while queue:
    if level & 1:  # This would reverse even levels (0-indexed)
        # reverse logic

Why This Fails:

• The root is at level 0 (even), its children at level 1 (odd)
• Starting at 1 would treat the root's children as even level
• Results in reversing the wrong levels

Correct Approach:

• Initialize level = 0
• Increment level AFTER processing all nodes at the current level
• Remember: level 1, 3, 5... are odd (where we want to reverse)