> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Reverse Odd Levels of Binary Tree

> Tested Python solution for LeetCode 2415 with 17 pytest cases. Generate a practice environment with lcpy.

LeetCode 2415, [Medium](/catalog/medium). Topics: [Tree](/catalog/topics/tree), [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Binary Tree](/catalog/topics/binary-tree). [View on LeetCode](https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/).

Generate this problem as a practice environment: tested reference solution, 17 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2415   # by problem number
lcpy gen -s reverse_odd_levels_of_binary_tree   # by problem name
```

## Problem

Given the `root` of a \<strong>perfect\</strong> binary tree, reverse the node values at each \<strong>odd\</strong> level of the tree.

For example, suppose the node values at level 3 are `[2,1,3,4,7,11,29,18]`, then it should become `[18,29,11,7,4,3,1,2]`.

Return \<em>the root of the reversed tree\</em>.

A binary tree is \<strong>perfect\</strong> if all parent nodes have two children and all leaves are on the same level.

The \<strong>level\</strong> of a node is the number of edges along the path between it and the root node.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2022/07/28/first_case1.png)

```
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](https://assets.leetcode.com/uploads/2022/07/28/second_case3.png)

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

```
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

* The number of nodes in the tree is in the range \[1, 2^14]
* 0 \<= Node.val \<= 10^5
* root is a perfect binary tree

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/reverse_odd_levels_of_binary_tree/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/reverse_odd_levels_of_binary_tree/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(w) for the level queue, w = 2^depth at the deepest level
    def reverse_odd_levels(self, root: TreeNode[int] | None) -> TreeNode[int] | None:
        if root is None:
            return None
        queue: deque[TreeNode[int]] = deque([root])
        depth = 0
        while queue:
            level = list(queue)
            if depth % 2 == 1:
                left = 0
                right = len(level) - 1
                while left < right:
                    level[left].val, level[right].val = level[right].val, level[left].val
                    left += 1
                    right -= 1
            queue = deque(
                child for node in level for child in (node.left, node.right) if child is not None
            )
            depth += 1
        return root
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(w) for the level queue, w = 2^depth at the deepest level |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.