2415. Reverse Odd Levels of Binary Tree - Detailed Explanation

Problem Statement

You are given the root of a perfect binary tree (a binary tree in which all leaves are on the same level, and every parent has two children). Your task is to reverse the node values at every odd level of the tree (i.e., levels 1, 3, 5, …) and then return the root of the modified tree. The root is considered level 0.

For example, consider the following perfect binary tree:

         2
       /   \
      3     5
     / \   / \
    8  13 21 34

• Level 0: [2]
• Level 1: [3, 5] (odd level)
• Level 2: [8, 13, 21, 34]

After reversing the nodes on the odd level (level 1), the tree becomes:

         2
       /   \
      5     3
     / \   / \
    8  13 21 34

Example 1
Input:

root = [2, 3, 5, 8, 13, 21, 34]

Output:

[2, 5, 3, 8, 13, 21, 34]

Explanation:
Only the nodes at level 1 are reversed: the nodes 3 and 5 swap their values.

Example 2
Consider a tree with three levels:
Input:

root = [7, 13, 11, 1, 4, 6, 5, 0, 9, 8, 2, 3, 10, 12, 14]

This corresponds to:

• Level 0: [7]
• Level 1: [13, 11]
• Level 2: [1, 4, 6, 5]
• Level 3: [0, 9, 8, 2, 3, 10, 12, 14]

Output:
After reversing the odd levels (levels 1 and 3), the tree becomes:

• Level 0: [7]
• Level 1: [11, 13]
• Level 2: [1, 4, 6, 5]
• Level 3: [14, 12, 10, 3, 2, 8, 9, 0]

Hints

1. Level Order Traversal:
   You can perform a breadth-first (level order) traversal of the tree. For each odd level, collect the nodes in an array, reverse the array, and then reassign the reversed values to the nodes.

2. Symmetric DFS (Two-Pointer Technique):
   Since the tree is perfect, every level is symmetric. You can perform a depth-first search (DFS) that traverses the tree in pairs (mirror images). At each odd level, swap the values of the paired nodes. This method avoids extra space for storing nodes and naturally exploits the tree’s symmetry.

Approach 1: Breadth-First Search (BFS)

Explanation

• Traversal: Use level order traversal to visit all nodes level by level.

• Collection: For each level, if it is an odd level, store the nodes’ references (or values) in an array.

• Reversal: Reverse the collected array.

• Assignment: Reassign the reversed values back to the nodes on that level.

Drawbacks

• You need extra space to store the nodes of each level.
• Although intuitive, it involves multiple passes: one for collecting values and one for reassigning them.

Approach 2: Depth-First Search (DFS) with Two-Pointer Technique (Optimal)

Explanation

• Pairing: Start by pairing the left and right children of the root (level 1).
• Swapping on Odd Levels: For any pair of nodes at the same odd level, swap their values.
• Recursive Traversal: Recurse on the next level by pairing:

  • The left child of the first node with the right child of the second node.

  • The right child of the first node with the left child of the second node.

• Stop Condition: When you reach the leaf nodes, stop the recursion.

Benefits

• Space Efficiency: This method works in-place and only uses O(h) extra space (the recursion stack), where h is the tree height.

• Time Efficiency: The entire tree is visited once, leading to O(n) time complexity.

Python Code