Reverse Odd Levels of Binary Tree

Med

#2199Time: 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.2 companies

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree

Companies

J.P. Morgan josh technology

Prompt

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:

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:

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, 2¹⁴].
0 <= Node.val <= 10⁵
root is a perfect binary tree.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

If the root is null, return null.
Initialize a queue q and add the root.
Initialize level = 0.
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.
Return root.

Walkthrough

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode reverseOddLevels(TreeNode root) {18        if (root == null) {19            return null;20        }21 22        Queue<TreeNode> q = new LinkedList<>();23        q.offer(root);24        int level = 0;25 26        while (!q.isEmpty()) {27            int levelSize = q.size();28            if (level % 2 != 0) {29                // Odd level: collect nodes and values, then reverse and update30                List<TreeNode> nodesAtLevel = new ArrayList<>();31                List<Integer> valsAtLevel = new ArrayList<>();32                for (int i = 0; i < levelSize; i++) {33                    TreeNode node = q.poll();34                    nodesAtLevel.add(node);35                    valsAtLevel.add(node.val);36                    if (node.left != null) {37                        q.offer(node.left);38                        q.offer(node.right);39                    }40                }41                42                // Reverse values and update nodes43                Collections.reverse(valsAtLevel);44                for (int i = 0; i < levelSize; i++) {45                    nodesAtLevel.get(i).val = valsAtLevel.get(i);46                }47            } else {48                // Even level: just traverse and add children to queue49                for (int i = 0; i < levelSize; i++) {50                    TreeNode node = q.poll();51                    if (node.left != null) {52                        q.offer(node.left);53                        q.offer(node.right);54                    }55                }56            }57            level++;58        }59        return root;60    }61}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Define a recursive function dfs(node1, node2, level).
Base Case: If node1 is null, return.
If level is odd: a. Swap the values of node1 and node2.
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)
In the main function, if root is not null, initiate the process by calling dfs(root.left, root.right, 1).
Return root.

Walkthrough

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode reverseOddLevels(TreeNode root) {18        if (root == null) {19            return null;20        }21        dfs(root.left, root.right, 1);22        return root;23    }24 25    private void dfs(TreeNode node1, TreeNode node2, int level) {26        // Base case: if nodes are null, we've reached the end of a branch27        if (node1 == null || node2 == null) {28            return;29        }30 31        // If the level is odd, swap the values32        if (level % 2 != 0) {33            int temp = node1.val;34            node1.val = node2.val;35            node2.val = temp;36        }37 38        // Recurse for the next level.39        // The key is to pair the "outer" children (node1.left, node2.right)40        // and the "inner" children (node1.right, node2.left).41        dfs(node1.left, node2.right, level + 1);42        dfs(node1.right, node2.left, level + 1);43    }44}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1/** * 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 ; } }

1/** * 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 ; } };

1# 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem