LeetCode 2415 - Reverse Odd Levels of Binary Tree

The problem asks us to reverse the values of nodes at odd levels of a perfect binary tree. A perfect binary tree is a tree in which every parent node has exactly two children and all leaves appear at the same depth.

leetcodemediumtreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 2415

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to reverse the values of nodes at odd levels of a perfect binary tree. A perfect binary tree is a tree in which every parent node has exactly two children and all leaves appear at the same depth. The root node is at level 0 (even), its children are at level 1 (odd), their children are at level 2 (even), and so on. Reversing an odd level means that the leftmost node swaps values with the rightmost node at that level, the second leftmost swaps with the second rightmost, and so forth, but the tree structure itself remains unchanged.

The input is the root node of a perfect binary tree, and the output is the same tree but with values at odd levels reversed. Constraints tell us that the number of nodes is reasonably large (up to 214), but the tree being perfect simplifies traversal because every level is completely filled. Node values are between 0 and 10^5, which means we do not need to worry about integer overflows in Python or Go.

Important edge cases include a tree with only one node (where there are no odd levels to reverse), and trees with minimal depth (depth 1 or 2). The problem guarantees a perfect binary tree, so we do not need to handle missing children.

Approaches

The brute-force approach would involve performing a level-order traversal (BFS), storing all nodes in a list by level, and then explicitly reversing the values for each odd level. This works because BFS naturally organizes nodes by level. After collecting the nodes, we can swap values for every odd level using two pointers. This approach is simple but requires O(n) extra space to store nodes for all levels, which can be inefficient for large trees.

The optimal approach uses a depth-first traversal (DFS) with two pointers. The key observation is that for a perfect binary tree, nodes at an odd level can be accessed in pairs: one from the left subtree and the corresponding one from the right subtree. We can recursively traverse the tree, pairing left and right children at each level. If the level is odd, we swap their values directly. This approach uses O(log n) space due to recursion (tree depth) and avoids storing all nodes, making it more memory-efficient while remaining simple.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) BFS to store all nodes, then reverse values at odd levels
Optimal O(n) O(h) = O(log n) DFS recursively swaps paired nodes at odd levels

Algorithm Walkthrough

  1. Start at the root of the tree. The root is at level 0 (even).
  2. Define a helper recursive function that takes two nodes (left and right) and the current level.
  3. If either node is None, return. This is the base case for recursion.
  4. If the current level is odd, swap the values of left and right.
  5. Recursively call the helper on the children of left and right in pairs: left.left with right.right, and left.right with right.left. Increment the level by 1 for the recursive call.
  6. Continue until all nodes at all odd levels are reversed.
  7. Return the root of the modified tree.

Why it works: The invariant is that for every pair of nodes at an odd level, we swap their values. Because the tree is perfect, every node at level l has a symmetric node on the opposite side of the tree, so swapping all such pairs produces the correct reversed values without disturbing the structure.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        def dfs(left: TreeNode, right: TreeNode, level: int):
            if not left or not right:
                return
            if level % 2 == 1:
                left.val, right.val = right.val, left.val
            dfs(left.left, right.right, level + 1)
            dfs(left.right, right.left, level + 1)
        
        dfs(root.left, root.right, 1)
        return root

Explanation: We define a DFS helper that pairs symmetric nodes. If the level is odd, we swap their values. The recursion proceeds until all nodes are processed. This avoids storing all nodes and is memory-efficient.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func reverseOddLevels(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    
    var dfs func(left, right *TreeNode, level int)
    dfs = func(left, right *TreeNode, level int) {
        if left == nil || right == nil {
            return
        }
        if level % 2 == 1 {
            left.Val, right.Val = right.Val, left.Val
        }
        dfs(left.Left, right.Right, level + 1)
        dfs(left.Right, right.Left, level + 1)
    }
    
    dfs(root.Left, root.Right, 1)
    return root
}

Explanation: The Go solution mirrors the Python approach. Nil checks replace Python's None. Swapping integers in Go is straightforward using tuple assignment syntax. Recursive depth is limited by the tree height, which is log(n) for a perfect tree.

Worked Examples

Example 1: [2,3,5,8,13,21,34]

Initial odd level nodes: [3,5] at level 1

After reversal: [5,3]

Level Original Reversed
0 [2] [2]
1 [3,5] [5,3]
2 [8,13,21,34] [8,13,21,34]

Example 3: [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]

Level 1 odd nodes: [1,2] → [2,1]

Level 3 odd nodes: [1,1,1,1,2,2,2,2] → [2,2,2,2,1,1,1,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once during DFS
Space O(h) = O(log n) Recursive call stack proportional to tree height

The time complexity is optimal as every node must be visited. Space complexity is efficient since it only depends on recursion depth rather than storing all nodes.

Test Cases

# Provided examples
assert Solution().reverseOddLevels(TreeNode(2, TreeNode(3), TreeNode(5))).left.val == 5  # level 1 reversed
assert Solution().reverseOddLevels(TreeNode(7, TreeNode(13), TreeNode(11))).right.val == 13  # level 1 reversed
root = TreeNode(0,
                TreeNode(1, TreeNode(0, TreeNode(1), TreeNode(1)), TreeNode(0, TreeNode(1), TreeNode(1))),
                TreeNode(2, TreeNode(0, TreeNode(2), TreeNode(2)), TreeNode(0, TreeNode(2), TreeNode(2))))
res = Solution().reverseOddLevels(root)
assert res.left.val == 2 and res.right.val == 1  # level 1
assert res.left.left.left.val == 2 and res.right.right.right.val == 1  # level 3

# Edge cases
assert Solution().reverseOddLevels(TreeNode(1)).val == 1  # single node
assert Solution().reverseOddLevels(TreeNode(1, TreeNode(2), TreeNode(3))).left.val == 3  # minimal tree
Test Why
Single node tree No odd level, tree remains unchanged
Minimal 3-node tree Tests basic odd level reversal
Larger tree with multiple odd levels Ensures algorithm correctly handles multiple levels

Edge Cases

  1. Single Node Tree: If the tree has only the root, there are no odd levels to reverse. The implementation returns immediately without recursion.
  2. Two-Level Tree: A tree with only root and its children tests that the algorithm correctly handles level 1 reversal. It swaps the left and right child values without touching deeper levels.
  3. Maximum Depth Tree: For a perfect binary tree with many levels, recursion depth may reach log(n). The solution correctly handles this because each recursion call is only for paired nodes, preventing unnecessary stack growth. The DFS approach ensures all odd levels are reversed symmetrically without extra memory.