# Reverse Odd Levels of Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reverse-odd-levels-of-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/reverse-odd-levels-of-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
Given the `root` of a **perfect** binary tree, reverse the node values at each **odd** 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 _the root of the reversed tree_.

A binary tree is **perfect** if all parent nodes have two children and all leaves are on the same level.

The **level** of a node is the number of edges along the path between it and the root node.

**Example 1:**

![](https://assets.glich.co/dsa/reverse-odd-levels-of-binary-tree/image0.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.glich.co/dsa/reverse-odd-levels-of-binary-tree/image1.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.

**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:** 
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, 214]`.
* `0 <= Node.val <= 105`
* `root` is a **perfect** binary tree.

# Approaches
## BFS Level-by-Level Reversal
This approach uses a Breadth-First Search (BFS) to traverse the tree level by level. For each odd-numbered level, it collects all the nodes and their corresponding values. It then reverses the list of values and updates the nodes with these new reversed values.
**Time:** O(N), where N is the total number of nodes. Each node is visited, enqueued, and dequeued once. For odd levels, nodes are visited an extra time to update values, but this doesn't change the overall linear complexity. · **Space:** O(N), where N is the total number of nodes. For a perfect binary tree, the last level contains about N/2 nodes, so the space for the queue is O(N). Additionally, the lists for nodes and values at an odd level can also take up to O(N) space.
**Pros:** Easy to understand and implement as it follows the standard BFS pattern.; Directly models the problem statement of processing level by level.
**Cons:** Requires significant extra space, proportional to the number of nodes in the largest level, which can be up to N/2.
### Explanation
We use a queue to perform a standard level-order traversal. A `level` variable is maintained, starting from 0 for the root. In each iteration of the main loop, we process all nodes at the current `level`. If the `level` is odd, we first iterate through all nodes at this level, storing the nodes themselves in one list (`nodesAtLevel`) and their values in another (`valsAtLevel`), while also enqueuing their children for the next level's processing. After collecting all nodes and values for the current odd level, we reverse the `valsAtLevel` list. Finally, we iterate through the collected nodes and assign the new reversed values. If the `level` is even, we simply traverse the nodes and enqueue their children without any value modification. We increment the `level` counter after processing each level and continue until the queue is empty.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        if (root == null) {
            return null;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int level = 0;

        while (!q.isEmpty()) {
            int levelSize = q.size();
            if (level % 2 != 0) {
                // Odd level: collect nodes and values, then reverse and update
                List<TreeNode> nodesAtLevel = new ArrayList<>();
                List<Integer> valsAtLevel = new ArrayList<>();
                for (int i = 0; i < levelSize; i++) {
                    TreeNode node = q.poll();
                    nodesAtLevel.add(node);
                    valsAtLevel.add(node.val);
                    if (node.left != null) {
                        q.offer(node.left);
                        q.offer(node.right);
                    }
                }
                
                // Reverse values and update nodes
                Collections.reverse(valsAtLevel);
                for (int i = 0; i < levelSize; i++) {
                    nodesAtLevel.get(i).val = valsAtLevel.get(i);
                }
            } else {
                // Even level: just traverse and add children to queue
                for (int i = 0; i < levelSize; i++) {
                    TreeNode node = q.poll();
                    if (node.left != null) {
                        q.offer(node.left);
                        q.offer(node.right);
                    }
                }
            }
            level++;
        }
        return root;
    }
}
```
### Algorithm
1. If the `root` is null, return null.
2. Initialize a queue `q` and add the `root`.
3. Initialize `level = 0`.
4. While `q` is not empty:
    a. Get the current level size `n = q.size()`.
    b. If `level` is odd:
        i. Create a list `nodesAtLevel` to store nodes of the current level.
        ii. Create a list `valsAtLevel` to store values of the current level.
        iii. For `i` from 0 to `n-1`:
            - Dequeue a node `curr = q.poll()`.
            - Add `curr` to `nodesAtLevel`.
            - Add `curr.val` to `valsAtLevel`.
            - If `curr.left` is not null, enqueue `curr.left` and `curr.right`.
        iv. Reverse the `valsAtLevel` list.
        v. For `i` from 0 to `n-1`:
            - Set `nodesAtLevel.get(i).val = valsAtLevel.get(i)`.
    c. Else (if `level` is even):
        i. For `i` from 0 to `n-1`:
            - Dequeue a node `curr = q.poll()`.
            - If `curr.left` is not null, enqueue `curr.left` and `curr.right`.
    d. Increment `level`.
5. Return `root`.

## Recursive DFS with Symmetric Swapping
This approach uses a Depth-First Search (DFS) recursion. It leverages the property of a perfect binary tree that for any two nodes `node1` and `node2` that are symmetric with respect to the center of a level, their subtrees are also symmetric. By swapping values of symmetric nodes at odd levels, we can achieve the reversal.
**Time:** O(N), where N is the total number of nodes. Each node is visited exactly once during the traversal. · **Space:** O(H) or O(log N), where H is the height of the tree. This space is used by the recursion call stack. For a perfect binary tree, H is logarithmic with respect to the number of nodes N.
**Pros:** Highly space-efficient, using only logarithmic space for the recursion stack.; Elegant and concise solution.
**Cons:** The logic of pairing symmetric nodes might be less intuitive to grasp initially compared to the straightforward level-by-level approach of BFS.
### Explanation
We define a helper recursive function, say `dfs(node1, node2, level)`. The initial call from the main function will be `dfs(root.left, root.right, 1)`, starting the process at level 1. The base case for the recursion is when `node1` (and `node2`) is null, at which point we simply return. Inside the recursive function, we check if the current `level` is odd. If it is, we swap the values of `node1` and `node2`. Regardless of whether a swap occurred, we continue the traversal to deeper levels. The crucial step is to make the correct recursive calls for the children. The left child of `node1` is symmetric to the right child of `node2`, so we recurse with `dfs(node1.left, node2.right, level + 1)`. Similarly, the right child of `node1` is symmetric to the left child of `node2`, leading to the call `dfs(node1.right, node2.left, level + 1)`. This process continues until we have traversed the entire tree.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        if (root == null) {
            return null;
        }
        dfs(root.left, root.right, 1);
        return root;
    }

    private void dfs(TreeNode node1, TreeNode node2, int level) {
        // Base case: if nodes are null, we've reached the end of a branch
        if (node1 == null || node2 == null) {
            return;
        }

        // If the level is odd, swap the values
        if (level % 2 != 0) {
            int temp = node1.val;
            node1.val = node2.val;
            node2.val = temp;
        }

        // Recurse for the next level.
        // The key is to pair the "outer" children (node1.left, node2.right)
        // and the "inner" children (node1.right, node2.left).
        dfs(node1.left, node2.right, level + 1);
        dfs(node1.right, node2.left, level + 1);
    }
}
```
### Algorithm
1. Define a recursive function `dfs(node1, node2, level)`.
2. Base Case: If `node1` is null, return.
3. If `level` is odd:
    a. Swap the values of `node1` and `node2`.
4. Make recursive calls for the next level with symmetric children:
    a. `dfs(node1.left, node2.right, level + 1)`
    b. `dfs(node1.right, node2.left, level + 1)`
5. In the main function, if `root` is not null, initiate the process by calling `dfs(root.left, root.right, 1)`.
6. Return `root`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode reverseOddLevels ( TreeNode root ) { Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); for ( int i = 0 ; ! q . isEmpty (); ++ i ) { List < TreeNode > t = new ArrayList <>(); for ( int k = q . size (); k > 0 ; -- k ) { var node = q . poll (); if ( i % 2 == 1 ) { t . add ( node ); } if ( node . left != null ) { q . offer ( node . left ); q . offer ( node . right ); } } for ( int l = 0 , r = t . size () - 1 ; l < r ; ++ l , -- r ) { var x = t . get ( l ). val ; t . get ( l ). val = t . get ( r ). val ; t . get ( r ). val = x ; } } return root ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * reverseOddLevels ( TreeNode * root ) { queue < TreeNode *> q { { root } }; for ( int i = 0 ; q . size (); ++ i ) { vector < TreeNode *> t ; for ( int k = q . size (); k ; -- k ) { TreeNode * node = q . front (); q . pop (); if ( i & 1 ) { t . push_back ( node ); } if ( node -> left ) { q . push ( node -> left ); q . push ( node -> right ); } } for ( int l = 0 , r = t . size () - 1 ; l < r ; ++ l , -- r ) { swap ( t [ l ] -> val , t [ r ] -> val ); } } return root ; } };
```

### Python

```python
# 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 ]: q = deque ([ root ]) i = 0 while q : if i & 1 : l , r = 0 , len ( q ) - 1 while l < r : q [ l ]. val , q [ r ]. val = q [ r ]. val , q [ l ]. val l , r = l + 1 , r - 1 for _ in range ( len ( q )): node = q . popleft () if node . left : q . append ( node . left ) q . append ( node . right ) i += 1 return root
```