Reverse Odd Levels of Binary Tree — Problem & Solution
Reverse Odd Levels of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Reverse Odd Levels of Binary Tree is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a perfect binary tree (every inner node has two children and every leaf is on the same level).
Reverse the order of the node values on every odd level — the root is level 0 — leaving the tree's shape as it is, and return the root.
Example 1
Input: root = [2,3,5,8,13,21,34]
Output: [2,5,3,8,13,21,34]
Explanation: Only level 1 is odd: [3, 5] becomes [5, 3].
Example 2
Input: root = [7,13,11]
Output: [7,11,13]
Explanation: Level 1 [13, 11] becomes [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: Levels 1 and 3 are reversed: [1, 2] → [2, 1] and [1, 1, 1, 1, 2, 2, 2, 2] → [2, 2, 2, 2, 1, 1, 1, 1].
Constraints
1 <= number of nodes <= 2^140 <= Node.val <= 10^5root is a perfect binary tree
Hints for Reverse Odd Levels of Binary Tree
Hint 1
Reversing a level swaps its first and last value, its second and second-to-last, and so on — mirror-image pairs.
Hint 2
In a perfect tree, if
aandbare mirror images, thena.leftmirrorsb.rightanda.rightmirrorsb.left.Hint 3
Walk mirror pairs together starting from
(root.left, root.right), swapping their values whenever the level is odd.
How to solve Reverse Odd Levels of Binary Tree
Reversing a level means swapping values between mirror-image nodes. Mirror pairs are easy to walk in a perfect tree: the children of a mirror pair (a, b) form the pairs (a.left, b.right) and (a.right, b.left).
Approach
- Call
walk(root.left, root.right, level = 1). - If the nodes are null, stop.
- If
levelis odd, swapa.valandb.val. - Recurse on
(a.left, b.right, level + 1)and(a.right, b.left, level + 1). - Return the root.
Why it works
The i-th node from the left on a level and the i-th from the right are mirror images about the root, and every node on a level below the root belongs to exactly one such pair reached from (root.left, root.right). Swapping each pair once reverses the level; even levels are visited but left alone.
Complexity
- Time —
O(n) - Space —
O(h) = O(log n) for the recursion
Pitfalls
- Swapping node pointers instead of values must also rewire the parents — swapping values is simpler.
- Do not swap a pair twice (once from each side), which would undo the reversal; walking pairs avoids that.
Reference solution
Python
from typing import Optional
def reverseOddLevels(root: Optional[TreeNode]) -> Optional[TreeNode]:
def walk(a, b, level):
if a is None or b is None:
return
if level % 2 == 1:
a.val, b.val = b.val, a.val
walk(a.left, b.right, level + 1)
walk(a.right, b.left, level + 1)
if root:
walk(root.left, root.right, 1)
return rootJava
public static TreeNode reverseOddLevels(TreeNode root) {
if (root != null) mirrorWalk(root.left, root.right, 1);
return root;
}
static void mirrorWalk(TreeNode a, TreeNode b, int level) {
if (a == null || b == null) return;
if (level % 2 == 1) { int t = a.val; a.val = b.val; b.val = t; }
mirrorWalk(a.left, b.right, level + 1);
mirrorWalk(a.right, b.left, level + 1);
}C++
void mirrorWalk(TreeNode* a, TreeNode* b, int level);
TreeNode* reverseOddLevels(TreeNode* root) {
if (root) mirrorWalk(root->left, root->right, 1);
return root;
}
void mirrorWalk(TreeNode* a, TreeNode* b, int level) {
if (!a || !b) return;
if (level % 2 == 1) swap(a->val, b->val);
mirrorWalk(a->left, b->right, level + 1);
mirrorWalk(a->right, b->left, level + 1);
}JavaScript
var reverseOddLevels = function(root) {
if (root !== null) mirrorWalk(root.left, root.right, 1);
return root;
};
var mirrorWalk = function(a, b, level) {
if (a === null || b === null) return;
if (level % 2 === 1) { var t = a.val; a.val = b.val; b.val = t; }
mirrorWalk(a.left, b.right, level + 1);
mirrorWalk(a.right, b.left, level + 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)