Watch 10 video solutions for Reverse Odd Levels of Binary Tree, a medium level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by codestorywithMIK has 8,435 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: Given the root of a perfect binary tree, reverse the node values at every odd level of the tree. Level 0 (the root) stays unchanged, level 1 gets reversed, level 2 stays the same, and so on. Only the values are swapped—tree structure remains unchanged.
Approach 1: Brute Force Method using Level Order Traversal (O(n) time, O(n) space)
This approach uses a classic Breadth-First Search to process the tree level by level. Use a queue to perform level order traversal and store nodes of the current level in an array. If the level index is odd, reverse the values in that array by swapping elements from both ends using a two-pointer technique. Then write the reversed values back into the nodes. The algorithm touches each node exactly once, so the time complexity is O(n), while the queue and temporary storage require O(n) space in the worst case.
This method is straightforward and easy to implement. It works well if you naturally think about trees in terms of levels. However, it temporarily stores an entire level of nodes, which adds extra memory overhead.
Approach 2: Optimized Symmetric DFS (O(n) time, O(h) space)
The optimized solution exploits the symmetry of a perfect binary tree. Instead of collecting values by level, traverse the tree in pairs of mirrored nodes using Depth-First Search. Start with the root's left and right children. When visiting a pair of symmetric nodes, check the current depth: if the depth is odd, swap their values. Then recursively process the pairs (left.left, right.right) and (left.right, right.left).
This technique directly swaps mirrored nodes without storing entire levels. Every node is visited once, giving O(n) time complexity. The recursion stack only grows to the height of the tree, which is O(h) (or O(log n) for a perfect tree). Because it avoids extra arrays or queues, the memory usage is significantly lower.
Recommended for interviews: The symmetric DFS approach is usually what interviewers expect. It shows you recognize the structural symmetry of a perfect binary tree and can leverage it for an efficient in-place solution. The brute force BFS method still demonstrates solid understanding of level-order traversal, but the DFS pairing technique highlights deeper tree manipulation skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Level Order Traversal (BFS) | O(n) | O(n) | When implementing a simple level-by-level traversal or when clarity is preferred over memory optimization |
| Symmetric DFS Node Pair Swapping | O(n) | O(h) | Best for perfect binary trees where mirrored nodes can be processed together with minimal extra memory |