Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.
[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.
Example 1:
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:
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:
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:
[1, 214].0 <= Node.val <= 105root is a perfect binary tree.The key idea in #2415 Reverse Odd Levels of Binary Tree is to reverse node values at every odd level while keeping the tree structure unchanged. Since the tree is a perfect binary tree, nodes at the same level have symmetric counterparts, which can be leveraged to efficiently swap values.
One common approach is to perform a Breadth-First Search (BFS) using a queue. While traversing level by level, store the nodes of each level and, when the level index is odd, reverse their values before continuing. This ensures that only node values change while the structure remains intact.
Another elegant method uses Depth-First Search (DFS) with two pointers moving simultaneously across symmetric nodes (left and right subtrees). When visiting an odd level, simply swap their values. This approach takes advantage of the tree’s symmetry.
Both strategies visit each node once, resulting in O(n) time complexity, where n is the number of nodes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search (Level Order) | O(n) | O(n) |
| Depth-First Search (Symmetric Traversal) | O(n) | O(h) |
codestorywithMIK
Use these hints if you're stuck. Try solving on your own first.
Try to solve recursively for each level independently.
While performing a depth-first search, pass the left and right nodes (which should be paired) to the next level. If the current level is odd, then reverse their values, or else recursively move to the next level.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A perfect binary tree guarantees that every internal node has two children and all leaves are at the same depth. This property allows symmetric traversal of left and right subtrees, making it easier to swap values at odd levels.
Yes, tree traversal problems like this are commonly discussed in technical interviews at major tech companies. The problem tests understanding of BFS, DFS, tree symmetry, and manipulation of node values across levels.
Queues are typically used for the BFS level-order traversal approach because they naturally process nodes level by level. For DFS solutions, recursion and the call stack help traverse symmetric nodes across the tree.
A common optimal strategy is to traverse the tree level by level using BFS and reverse node values on odd levels. Another efficient approach uses DFS with symmetric node pairs, swapping values whenever the current depth is odd.