#2415

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Reverse Odd Levels of Binary Tree

Reverse the node values at each odd level in a perfect binary tree, preserving the even levels.

tree depth first search breadth first search binary tree

Problem Statement

Given the root of a perfect binary tree, reverse the values of nodes at each odd level, while leaving the even levels unchanged. A perfect binary tree is defined as a tree where each non-leaf node has exactly two children, and all leaves are at the same level.

You need to return the root of the modified tree with the values reversed only on the odd levels. The goal is to implement an efficient approach to achieve this reversal and ensure that the tree structure remains intact.

Examples

Example 1

Input: root = [2,3,5,8,13,21,34]

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

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

Input: root = [7,13,11]

Output: [7,11,13]

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]

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.

Solution Approach

Level-wise Traversal with State Tracking

To solve this problem, perform a level-wise traversal using either Depth-First Search (DFS) or Breadth-First Search (BFS). At each odd level, store the node values in a list and reverse them. After reversing, assign the reversed values back to their respective nodes.

Recursive Solution

Another approach is to use recursion to traverse each level of the tree. When an odd level is encountered, store the values of nodes and reverse them. This method leverages recursion to traverse the tree in a top-down manner while reversing nodes only on odd levels.

Space Optimization

In some cases, optimizing space is important. Instead of storing the entire list of values at each odd level, you can use a two-pointer technique or modify the tree in-place. This minimizes the space complexity, though the logic for maintaining node order and reversal still applies.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity for this solution is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once during the traversal. The space complexity is O(n) as well, due to the space required to store node values during the reversal process or for the recursive call stack in case of recursion.

What Interviewers Usually Probe

Candidates should be able to implement binary tree traversal techniques efficiently.
Look for the candidate's ability to identify and reverse values at odd levels correctly.
Assess if the candidate can optimize space complexity while ensuring the problem's constraints are met.

Common Pitfalls or Variants

Common pitfalls

Incorrectly reversing nodes at even levels instead of odd levels.
Failing to maintain the tree structure during reversal, causing the tree to become unbalanced.
Not handling edge cases where the tree has very few nodes, such as a single-node tree or a tree with only two levels.

Follow-up variants

Consider implementing the solution iteratively rather than recursively.
Challenge the candidate to optimize for space by modifying the tree in-place.
Extend the problem to reverse values on both odd and even levels or implement other forms of level-wise node manipulation.

FAQ

How can I reverse the values at odd levels of a binary tree?

You can reverse the values by performing a level-order traversal, identifying odd levels, and reversing the values of nodes at those levels.

What is a perfect binary tree?

A perfect binary tree is a binary tree where each non-leaf node has exactly two children, and all leaves are at the same level.

What traversal method is best for this problem?

Both Depth-First Search (DFS) and Breadth-First Search (BFS) can be used effectively. BFS is particularly useful for level-order traversal.

How do I handle edge cases like a single-node tree?

For a single-node tree, there are no odd levels to reverse, so the tree remains unchanged.

Can I optimize space usage for this problem?

Yes, you can minimize space usage by reversing the nodes in-place or using a two-pointer technique instead of storing all values at odd levels.

terminal

Solution

Solution 1: BFS

We can use the Breadth-First Search (BFS) method, using a queue $q$ to store the nodes of each level, and a variable $i$ to record the current level. If $i$ is odd, we reverse the values of the nodes at the current level.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

# 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

Continue Practicing

#2385 amount of time for binary tree to be infected #2458 height of binary tree after subtree removal queries #2641 cousins in binary tree ii