Reverse Odd Levels of Binary Tree

medium tree bfs dfs

Problem

You are given the root of a perfect binary tree (every level is completely filled). Number the levels starting at 0 for the root. Reverse the node values on every odd-numbered level — level 1, level 3, level 5, and so on — while leaving even levels untouched. Reversing a level means the value of the leftmost node swaps with the rightmost, the second-from-left swaps with the second-from-right, and so on. Return the root of the modified tree.

The tree shape never changes; only the values stored on odd levels move. A level-order (BFS) sweep makes this clean: collect the nodes of each level, and on odd levels swap values from the two ends toward the middle.

Inputlevel-order: [2, 3, 5, 8, 13, 21, 34]

Output[2, 5, 3, 8, 13, 21, 34]

Level 0 is [2] (kept). Level 1 is [3, 5]; reversing gives [5, 3]. Level 2 [8, 13, 21, 34] is even, so it is kept. The result is [2, 5, 3, 8, 13, 21, 34].

level-order (perfect tree)

from collections import deque
def reverse_odd_levels(root):
    q = deque([root])
    level = 0
    while q:
        nodes = list(q)
        if level % 2 == 1:
            i, j = 0, len(nodes) - 1
            while i < j:
                nodes[i].val, nodes[j].val = nodes[j].val, nodes[i].val
                i, j = i + 1, j - 1
        for _ in range(len(q)):
            node = q.popleft()
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        level += 1
    return root

function reverseOddLevels(root) {
  let q = [root];
  let level = 0;
  while (q.length) {
    const nodes = q;
    if (level % 2 === 1) {
      let i = 0, j = nodes.length - 1;
      while (i < j) {
        const t = nodes[i].val; nodes[i].val = nodes[j].val; nodes[j].val = t;
        i++; j--;
      }
    }
    const next = [];
    for (const node of nodes) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    q = next;
    level++;
  }
  return root;
}

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        List<TreeNode> q = new ArrayList<>();
        q.add(root);
        int level = 0;
        while (!q.isEmpty()) {
            List<TreeNode> nodes = q;
            if (level % 2 == 1) {
                int i = 0, j = nodes.size() - 1;
                while (i < j) {
                    int t = nodes.get(i).val;
                    nodes.get(i).val = nodes.get(j).val;
                    nodes.get(j).val = t;
                    i++; j--;
                }
            }
            List<TreeNode> next = new ArrayList<>();
            for (TreeNode node : nodes) {
                if (node.left != null) next.add(node.left);
                if (node.right != null) next.add(node.right);
            }
            q = next;
            level++;
        }
        return root;
    }
}

TreeNode* reverseOddLevels(TreeNode* root) {
    vector<TreeNode*> q = { root };
    int level = 0;
    while (!q.empty()) {
        vector<TreeNode*>& nodes = q;
        if (level % 2 == 1) {
            int i = 0, j = (int)nodes.size() - 1;
            while (i < j) {
                swap(nodes[i]->val, nodes[j]->val);
                i++; j--;
            }
        }
        vector<TreeNode*> next;
        for (TreeNode* node : nodes) {
            if (node->left) next.push_back(node->left);
            if (node->right) next.push_back(node->right);
        }
        q = next;
        level++;
    }
    return root;
}

Explanation

The tree is perfect, so every level is full: level 0 has 1 node, level 1 has 2, level 2 has 4, and in general level k has 2^k nodes. We only need to flip the values on the odd levels and leave everything else exactly where it is.

The cleanest approach is a level-order BFS. We keep a list of the nodes on the current level. We also keep a level counter that starts at 0 for the root. For each level we ask one question: is level odd?

If the level is odd, we reverse its values using two pointers. One pointer i starts at the left end and one pointer j starts at the right end. We swap the values they point to, then step i right and j left, until they meet in the middle. Notice we swap only the val fields — the nodes themselves and the tree links stay put.

After handling the current level (whether we reversed it or not), we build the next level by collecting the children of every node, left child before right child. Then we bump level and repeat until the queue is empty.

Example: [2, 3, 5, 8, 13, 21, 34]. Level 0 is [2] — even, untouched. Level 1 is [3, 5] — odd, so swap the ends to get [5, 3]. Level 2 is [8, 13, 21, 34] — even, untouched. The tree now reads [2, 5, 3, 8, 13, 21, 34].

A recursive variant exists too: walk down the two mirror nodes of each level together (left child of one side paired with the right child of the other), swapping their values when you are about to enter an odd level. Both run in linear time.

Time: O(n) Space: O(w) level width