2415. Reverse Odd Levels of Binary Tree


Problem Description

In this problem, we are given a root of a perfect binary tree and are asked to reverse the node values at each odd level of the tree. To clarify, the level of a node is defined by the number of edges along the path from the node to the root node. Level 0 is where the root node itself is. Therefore, the first set of nodes for which we will reverse values is at level 1.

For example, if a given tree has node values [2,1,3,4,7,11,29,18] at level 3, after the reversal, the node values at this level should be [18,29,11,7,4,3,1,2]. We then return the root of the modified tree where these reversals have been applied to all odd levels.

Note that a perfect binary tree is one where every non-leaf node has exactly two children and all leaf nodes are at the same level (the bottommost level).

Intuition

The basic idea to solve this problem is to traverse the tree level by level, also known as level-order traversal. This can be efficiently performed using a queue. We will process all nodes on the same level before moving on to the next. At each step, we'll keep track of which level we're currently processing.

  1. If we're at an even level, we don't need to reverse the nodes, and we simply continue with the traversal.
  2. If we're at an odd level, however, we need to reverse the values of the nodes at that level.

Given that a perfect binary tree at level i has 2^i nodes, we can reverse the nodes by simply swapping the values of nodes at symmetrical positions in the level: first node with the last, second node with the second to last, and so on until we reach the center of the level.

So for each level, especially for odd ones, we will:

  • Store nodes in a temporary list.
  • Use two pointers method to reverse the values in the temporary list.
  • Continue the traversal for all levels.

This way we do not create a new tree rather we just modify the existing tree nodes' values where needed which is a memory-efficient way to handle the problem.

So, the solution uses a breadth-first search to traverse the tree levels and two pointers technique to swap the nodes' values at odd levels.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which technique can we use to find the middle of a linked list?

Solution Approach

The solution follows a level-order traversal pattern using a queue, which is a common approach to process each level of a tree independently. Let's break down the code implementation step by step.

  1. The code first initializes a queue q with the root node in it.

  2. A variable i is used to keep track of the current level, starting at 0 for the root.

  3. The outer while loop runs as long as there are nodes left in the queue (which means there are more levels to process). For each iteration of this loop, we are dealing with nodes on a single level.

    1q = deque([root])
    2i = 0
    3while q:
    4    # ...
    5    i += 1
  4. Inside the loop, a temporary list t is created to keep track of the nodes at the current level, if the level is odd.

  5. An inner for loop then iterates over each node in the current level (which was populated from the parent level). During this process, it:

    • Pops nodes from the left of the queue (FIFO).
    • Checks if the current level i is odd. If so, the node is appended to list t for later reversal.
    • Enqueues the left and right children of the current node if they exist.
    1t = []
    2for _ in range(len(q)):
    3    node = q.popleft()
    4    if i & 1:
    5        t.append(node)
    6    if node.left:
    7        q.append(node.left)
    8    if node.right:
    9        q.append(node.right)
  6. After the inner loop, the nodes that need to be reversed are now in the list t if the level i is odd. The code then reverses the values of these nodes using two pointers:

    • One pointer starts at the beginning of the list j and another at the end k.
    • As long as j is less than k, we swap the values of the nodes at these two indexes.
    • Then the pointers are moved towards each other and the process repeats until all the node values are reversed.
    1if t:
    2    j, k = 0, len(t) - 1
    3    while j < k:
    4        t[j].val, t[k].val = t[k].val, t[j].val
    5        j, k = j + 1, k - 1
  7. At the end of the outer loop, the level i is incremented, and the loop continues to the next level.

At the conclusion of these steps, we've modified the original tree so that all the values at the odd levels are reversed as per the problem statement. The root of the modified tree is returned at the end of the function.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example Walkthrough

Let's consider a perfect binary tree with the following node values:

1        1
2       / \
3      2   3
4     / \ / \
5    4  5 6  7

We should reverse the node values at each odd level (1, 3, 5, ...). Level 0, which is where the root is (1), will not be reversed, but level 1 with nodes 2 and 3 should be reversed.

Let's execute the solution approach step by step:

  1. We initialize a queue q with the root node (1) in it. We also set our level tracker i to 0.

    1q = deque([1])
    2i = 0
  2. We then enter the outer while loop, starting to process level 0 (we are at the root node 1 now).

  3. Since level 0 is even, we don't reverse anything. We enqueue its children (2 and 3) to the queue.

    After this step, our queue will look like this:

    1q = deque([2, 3])
    2i = 1  # Increment level tracker
  4. Now we are at level 1 which is odd. So we need to reverse the node values at this level.

  5. We iterate over nodes at level 1 and put them in a temporary list t, and at the same time enqueue their children. Our queue becomes deque([4, 5, 6, 7]) and t = [2, 3].

  6. After the previous step, we're still in the outer loop where i is 1, and now we reverse the nodes in t. After the swap, t will be [3, 2].

  7. Completing the level, we go to level 2, and since it's even, we just enqueue the child nodes (which in this case, do not exist since it's the last level). Now the queue is empty, and the loop exits.

The final tree structure after the reversal will look like this:

1        1
2       / \
3      3   2
4     / \ / \
5    4  5 6  7

Note that only the odd level (level 1) values were reversed, and the even levels (levels 0 and 2) remained unchanged. The root of this modified tree will then be returned by the function.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
5        # Create a queue using deque for level-order traversal.
6        queue = deque([root])
7      
8        # Initialize a level indicator, starting with level 0 for the root.
9        level = 0
10      
11        # Start the level order traversal of the tree.
12        while queue:
13            # Temporary list to hold the nodes at the current level.
14            current_level_nodes = []
15          
16            # Iterate over nodes at the current level.
17            for _ in range(len(queue)):
18                node = queue.popleft()  # Remove the node from the queue.
19              
20                # If the current level is odd, add the node to the temporary list.
21                if level % 2 == 1:
22                    current_level_nodes.append(node)
23              
24                # Add the children of the node to the queue for the next level.
25                if node.left:
26                    queue.append(node.left)
27                if node.right:
28                    queue.append(node.right)
29          
30            # If we have nodes at the current level and the level is odd,
31            # reverse the values of the nodes at this level.
32            if current_level_nodes:
33                left, right = 0, len(current_level_nodes) - 1
34                while left < right:
35                    # Swap the values of the nodes.
36                    current_level_nodes[left].val, current_level_nodes[right].val = current_level_nodes[right].val, current_level_nodes[left].val
37                    left += 1
38                    right -= 1
39          
40            # Move to the next level in the tree.
41            level += 1
42      
43        # Return the modified tree.
44        return root
45
1class Solution {
2    public TreeNode reverseOddLevels(TreeNode root) {
3        // Queue for performing level order traversal
4        Deque<TreeNode> queue = new ArrayDeque<>();
5        queue.offer(root);
6      
7        // Level marker, starting from 0 (root level)
8        int level = 0;
9      
10        // Loop through levels of the tree
11        while (!queue.isEmpty()) {
12            // Temporary list to hold nodes of the current level
13            List<TreeNode> currentLevelNodes = new ArrayList<>();
14          
15            // Iterate over all nodes at the current level
16            for (int count = queue.size(); count > 0; count--) {
17                // Retrieve and remove the head of the queue
18                TreeNode node = queue.pollFirst();
19              
20                // If we're on an odd level, add the node to our list
21                if (level % 2 == 1) {
22                    currentLevelNodes.add(node);
23                }
24              
25                // If left child exists, add it to the queue for next level
26                if (node.left != null) {
27                    queue.offer(node.left);
28                }
29              
30                // If right child exists, add it to the queue for next level
31                if (node.right != null) {
32                    queue.offer(node.right);
33                }
34            }
35          
36            // If the current level is odd, we reverse the values of the nodes at this level
37            if (!currentLevelNodes.isEmpty()) {
38                int startIndex = 0;
39                int endIndex = currentLevelNodes.size() - 1;
40              
41                // Swap the values of nodes from start to end until they reach the middle
42                while (startIndex < endIndex) {
43                    // Swapping values of the node
44                    int tempVal = currentLevelNodes.get(startIndex).val;
45                    currentLevelNodes.get(startIndex).val = currentLevelNodes.get(endIndex).val;
46                    currentLevelNodes.get(endIndex).val = tempVal;
47                  
48                    // Move towards the center
49                    startIndex++;
50                    endIndex--;
51                }
52            }
53          
54            // Move to next level
55            level++;
56        }
57      
58        // Return the modified tree
59        return root;
60    }
61}
62
1#include <queue>
2#include <vector>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode() : val(0), left(nullptr), right(nullptr) {}
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    // The function takes a root node of a binary tree and reverses the nodes at odd levels of the tree.
17    TreeNode* reverseOddLevels(TreeNode* root) {
18        std::queue<TreeNode*> queue{{root}}; // Initialize a queue to facilitate level order traversal.
19        int level = 0; // Start from level 0 (which is the root level).
20        std::vector<TreeNode*> nodesToReverse; // This vector holds nodes of the current level.
21
22        // While there are still nodes left to process in the queue
23        while (!queue.empty()) {
24            nodesToReverse.clear(); // Clear the vector for the new level of nodes.
25            for (int n = queue.size(); n > 0; --n) {
26                TreeNode* currentNode = queue.front(); // Get the front node from the queue.
27                queue.pop(); // Pop the front node.
28
29                // If we are at an odd level, collect the nodes to be reversed.
30                if (level % 2 == 1) {
31                    nodesToReverse.push_back(currentNode);
32                }
33              
34                // If left child exists, push it onto the queue for the next level's traversal.
35                if (currentNode->left) {
36                    queue.push(currentNode->left);
37                }
38                // If right child exists, push it onto the queue too.
39                if (currentNode->right) {
40                    queue.push(currentNode->right);
41                }
42            }
43
44            // Reverse the node values if we have collected any nodes.
45            if (!nodesToReverse.empty()) {
46                int left = 0; // Start from the first node in the vector.
47                int right = nodesToReverse.size() - 1; // And the last node.
48                while (left < right) {
49                    // Swap values of the node pair.
50                    std::swap(nodesToReverse[left]->val, nodesToReverse[right]->val);
51                    ++left;
52                    --right;
53                }
54            }
55            ++level; // Increment the level count after processing all nodes at current level.
56        }
57
58        return root; // Return the updated tree.
59    }
60};
61
1/**
2 * Definition for a tree node.
3 */
4class TreeNode {
5    val: number;
6    left: TreeNode | null;
7    right: TreeNode | null;
8
9    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
10        this.val = val === undefined ? 0 : val;
11        this.left = left === undefined ? null : left;
12        this.right = right === undefined ? null : right;
13    }
14}
15
16/**
17 * Reverses the values of nodes at odd levels of the binary tree.
18 * @param {TreeNode | null} root - The root node of the binary tree.
19 * @returns {TreeNode | null} - The root node of the modified binary tree.
20 */
21function reverseOddLevels(root: TreeNode | null): TreeNode | null {
22    const queue: (TreeNode | null)[] = [root]; // Initialize a queue for level order traversal.
23    let depth = 0; // Initialize tree depth.
24
25    // Perform a level order traversal using a queue.
26    while (queue.length !== 0) {
27        const levelSize = queue.length; // Number of nodes at the current level.
28        const currentLevelNodes: TreeNode[] = []; // Holds nodes of the current level if the level is odd.
29
30        // Process nodes by their level.
31        for (let i = 0; i < levelSize; i++) {
32            const node = queue.shift();
33            if (node) {
34                // On odd levels, add the nodes to the currentLevelNodes array for later reversal.
35                if (depth % 2 === 1) {
36                    currentLevelNodes.push(node);
37                }
38
39                // Enqueue child nodes for the next level.
40                if (node.left) queue.push(node.left);
41                if (node.right) queue.push(node.right);
42            }
43        }
44
45        // If the current level is odd, reverse the values of nodes at this current level.
46        if (depth % 2 === 1) {
47            const middleIndex = currentLevelNodes.length >> 1; // Get the midpoint index.
48            for (let i = 0; i < middleIndex; i++) {
49                // Swap values between symmetric nodes.
50                const mirrorIndex = currentLevelNodes.length - 1 - i;
51                [currentLevelNodes[i].val, currentLevelNodes[mirrorIndex].val] = [currentLevelNodes[mirrorIndex].val, currentLevelNodes[i].val];
52            }
53        }
54
55        // Increment depth after each level.
56        depth++;
57    }
58
59    // Return the root of the modified tree.
60    return root;
61}
62
Not Sure What to Study? Take the 2-min Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Time and Space Complexity

Time Complexity

The provided code executes a breadth-first traversal on a binary tree to reverse the values at the odd levels. For each level of the tree, each node is processed exactly once.

  • The while loop runs for every level in the tree, so its runtime is O(h) where h is the height of the tree.
  • Inside the while loop, the for loop runs for all nodes at the current level (2^i nodes at level i).
  • As the tree is processed level by level, in total, all nodes in the tree are processed exactly once.

Thus, the total time complexity of this algorithm is proportional to the number of nodes in the tree. If the number of nodes in the tree is N, the time complexity is O(N).

Space Complexity

  • The queue q stores a maximum number of nodes equivalent to the width of the tree at its widest level, which, for a complete binary tree, would be O(N/2) or simplified as O(N), where N is the total number of nodes.
  • The list t stores nodes only at the current level and only at odd levels. In the worst case, this would be the width of the tree at its widest level, thus also O(N/2) or simplified as O(N).
  • Additionally, there are constant space overheads for the variables i, j, k, and references.

Therefore, the space complexity of the code is O(N).

Note: In the case where the binary tree is not complete or perfectly balanced, the width can be smaller than N/2, and hence the space complexity would be better than the worst-case scenario. However, for complexity analysis, we usually consider worst-case scenarios.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫