Problem

Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.

  • For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18], then it should become [18,29,11,7,4,3,1,2].

Return the root of the reversed tree.

A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.

The level of a node is the number of edges along the path between it and the root node.

Examples

Example 1:

graph LR
    subgraph Input
        A1[2]
        A1 --> B1[[3]]
        A1 --> C1[[5]]
        B1 --> D1[8]
        B1 --> E1[13]
        C1 --> F1[21]
        C1 --> G1[34]
        
        style B1 fill:#FFD580,stroke:#333,stroke-width:2px
        style C1 fill:#ADD8E6,stroke:#333,stroke-width:2px
    end
    
    subgraph Output
        A2[2]
        A2 --> B2[[5]]
        A2 --> C2[[3]]
        B2 --> F2[34]
        B2 --> G2[21]
        C2 --> D2[8]
        C2 --> E2[13]
        
        style C2 fill:#FFD580,stroke:#333,stroke-width:2px
        style B2 fill:#ADD8E6,stroke:#333,stroke-width:2px
    end
    
    Input --> Output
  
1
2
3
4
5

Input: root = [2,3,5,8,13,21,34]
Output: [2,5,3,8,13,21,34]
Explanation: 
The tree has only one odd level.
The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.

Example 2:

graph LR
    subgraph Input
        A1[7]
        A1 --> B1[[13]]
        A1 --> C1[[11]]
        
        style B1 fill:#FFD580,stroke:#333,stroke-width:2px
        style C1 fill:#ADD8E6,stroke:#333,stroke-width:2px
    end
    
    subgraph Output
        A2[7]
        A2 --> B2[[11]]
        A2 --> C2[[13]]
        
        style C2 fill:#FFD580,stroke:#333,stroke-width:2px
        style B2 fill:#ADD8E6,stroke:#333,stroke-width:2px
    end
    
    Input --> Output
  
1
2
3
4

Input: root = [7,13,11]
Output: [7,11,13]
Explanation: 
The nodes at level 1 are 13, 11, which are reversed and become 11, 13.

Example 3:

1
2
3
4
5
6

Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
Explanation: 
The odd levels have non-zero values.
The nodes at level 1 were 1, 2, and are 2, 1 after the reversal.
The nodes at level 3 were 1, 1, 1, 1, 2, 2, 2, 2, and are 2, 2, 2, 2, 1, 1, 1, 1 after the reversal.

Constraints:

  • The number of nodes in the tree is in the range [1, 214].
  • 0 <= Node.val <= 10^5
  • root is a perfect binary tree.

Solution

Method 1 - BFS

To reverse the node values at each odd level of a perfect binary tree, we can perform a level-order traversal (BFS - Breadth-First Search) while keeping track of the nodes at each level. For each odd level, we reverse the node values.

Here is the approach:

  1. Perform a BFS traversal to access nodes level by level.
  2. Store the nodes at each level.
  3. For each odd level, reverse the values of the nodes.
  4. Assign the reversed values back to the corresponding nodes.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<TreeNode> levelNodes = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelNodes.add(node);
                if (node.left != null) {
	                queue.add(node.left);
	            }
                if (node.right != null) {
	                queue.add(node.right);
	            }
            }
            
            if (level % 2 == 1) {
                reverseLevelValues(levelNodes);
            }
            
            level++;
        }
        
        return root;
    }
    
    private void reverseLevelValues(List<TreeNode> levelNodes) {
        int i = 0, j = levelNodes.size() - 1;
        while (i < j) {
            int temp = levelNodes.get(i).val;
            levelNodes.get(i).val = levelNodes.get(j).val;
            levelNodes.get(j).val = temp;
            i++;
            j--;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        queue = deque([root])
        level = 0
        
        while queue:
            size = len(queue)
            level_nodes = []
            
            for _ in range(size):
                node = queue.popleft()
                level_nodes.append(node)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            if level % 2 == 1:
                self._reverse_values(level_nodes)
            
            level += 1
        
        return root
    
    def _reverse_values(self, level_nodes: list[TreeNode]) -> None:
        i, j = 0, len(level_nodes) - 1
        while i < j:
            level_nodes[i].val, level_nodes[j].val = level_nodes[j].val, level_nodes[i].val
            i += 1
            j -= 1

Complexity

  • ⏰ Time complexity: O(n), as the algorithm requires traversing each node once
  • 🧺 Space complexity: O(n) uses extra space to store nodes by levels,