Reverse Odd Levels of Binary Tree

Medium
1958.

Reverse Odd Levels of Binary Tree

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.

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^14
  • 0 <= Node.val <= 10^5
  • root is a perfect binary tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var reverseOddLevels = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^14
  • 0 <= Node.val <= 10^5
  • root is a perfect binary tree

Hints for Reverse Odd Levels of Binary Tree

  1. Hint 1

    Reversing a level swaps its first and last value, its second and second-to-last, and so on — mirror-image pairs.

  2. Hint 2

    In a perfect tree, if a and b are mirror images, then a.left mirrors b.right and a.right mirrors b.left.

  3. 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

  1. Call walk(root.left, root.right, level = 1).
  2. If the nodes are null, stop.
  3. If level is odd, swap a.val and b.val.
  4. Recurse on (a.left, b.right, level + 1) and (a.right, b.left, level + 1).
  5. 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 root

Java

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)