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).
Flowchart Walkthrough
Let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
-
Is it a graph?
- Yes: A Binary Tree is a special form of a graph.
-
Is it a tree?
- Yes: Specifically, it is a Binary Tree.
-
DFS
- Given the tree structure, and since the problem specifically involves manipulating levels of a binary tree (reversing values at odd levels), using Depth-First Search (DFS) is appropriate. DFS allows us to manage and track the level during the traversal effectively.
Conclusion: Following the flowchart confirms that Depth-First Search (DFS) is suitable for this problem where a tree structure is manipulated by level-specific operations.
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.
- If we're at an even level, we don't need to reverse the nodes, and we simply continue with the traversal.
- 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.
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.
-
The code first initializes a queue
q
with the root node in it. -
A variable
i
is used to keep track of the current level, starting at 0 for the root. -
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.q = deque([root]) i = 0 while q: # ... i += 1
-
Inside the loop, a temporary list
t
is created to keep track of the nodes at the current level, if the level is odd. -
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 listt
for later reversal. - Enqueues the left and right children of the current node if they exist.
t = [] for _ in range(len(q)): node = q.popleft() if i & 1: t.append(node) if node.left: q.append(node.left) if node.right: q.append(node.right)
-
After the inner loop, the nodes that need to be reversed are now in the list
t
if the leveli
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 endk
. - As long as
j
is less thank
, 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.
if t: j, k = 0, len(t) - 1 while j < k: t[j].val, t[k].val = t[k].val, t[j].val j, k = j + 1, k - 1
- One pointer starts at the beginning of the list
-
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a perfect binary tree with the following node values:
1 / \ 2 3 / \ / \ 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:
-
We initialize a queue
q
with the root node (1
) in it. We also set our level trackeri
to 0.q = deque([1]) i = 0
-
We then enter the outer while loop, starting to process level 0 (we are at the root node
1
now). -
Since level 0 is even, we don't reverse anything. We enqueue its children (
2
and3
) to the queue.After this step, our queue will look like this:
q = deque([2, 3]) i = 1 # Increment level tracker
-
Now we are at level 1 which is odd. So we need to reverse the node values at this level.
-
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 becomesdeque([4, 5, 6, 7])
andt = [2, 3]
. -
After the previous step, we're still in the outer loop where
i
is 1, and now we reverse the nodes int
. After the swap,t
will be[3, 2]
. -
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 / \ 3 2 / \ / \ 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
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)
whereh
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 leveli
). - 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 beO(N/2)
or simplified asO(N)
, whereN
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 alsoO(N/2)
or simplified asO(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.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Want a Structured Path to Master System Design Too? Donāt Miss This!