Reverse Odd Levels of Binary Tree

class Solution {
public:
    TreeNode* invertOddLevels(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;  // Early return if root is null.
        }
    
        queue<TreeNode*> queueNodes;
        queueNodes.push(root);  // Begin BFS traversal from the root.
        int depth = 0;
    
        while (!queueNodes.empty()) {
            int levelSize = queueNodes.size();
            vector<TreeNode*> nodesAtLevel;
    
            // Gather all nodes of this level.
            for (int index = 0; index < levelSize; index++) {
                TreeNode* currentNode = queueNodes.front();
                queueNodes.pop();
                nodesAtLevel.push_back(currentNode);
    
                if (currentNode->left) queueNodes.push(currentNode->left);
                if (currentNode->right) queueNodes.push(currentNode->right);
            }
    
            // Reverse values at odd levels.
            if (depth % 2 == 1) {
                int start = 0, end = nodesAtLevel.size() - 1;
                while (start < end) {
                    swap(nodesAtLevel[start]->val, nodesAtLevel[end]->val);
                    start++;
                    end--;
                }
            }
    
            depth++;
        }
    
        return root;  // Return modified root.
    }
};

The provided C++ solution focuses on reversing the values of nodes at odd levels of a binary tree. Here's a comprehensive breakdown of how the code achieves this:

• The function invertOddLevels starts by checking if the root is nullptr, returning nullptr if true.
• The function uses Breadth-First Search (BFS) for tree traversal, initiating this process with a queue queueNodes.
• Nodes are traversed level-wise. For each level, all nodes are collected in a vector nodesAtLevel.
• If the current depth is an odd number (odd level in the tree), the values of nodes at this level are reversed. This reversal is accomplished by swapping values from the start and end of the nodesAtLevel vector progressively towards the center.
• The traversal and potential value reversal continue until all levels are processed.

This solution effectively modifies the tree in-place and ensures that node values at odd levels are reversed, thus providing a correctly modified binary tree structure. The BFS strategy ensures that all nodes at each level are accessible for potential modification, and the use of vectors and swapping helps efficiently manage the reversible operations.

class Solution {
    
    public TreeNode invertOddLevels(TreeNode rootNode) {
        if (rootNode == null) {
            return null;
        }
    
        Queue<TreeNode> bfsQueue = new LinkedList<>();
        bfsQueue.add(rootNode);
        int depth = 0;
    
        while (!bfsQueue.isEmpty()) {
            int count = bfsQueue.size();
            List<TreeNode> levelNodes = new ArrayList<>();
    
            for (int i = 0; i < count; i++) {
                TreeNode current = bfsQueue.poll();
                levelNodes.add(current);
    
                if (current.left != null) bfsQueue.add(current.left);
                if (current.right != null) bfsQueue.add(current.right);
            }
    
            if (depth % 2 == 1) {
                int start = 0, end = levelNodes.size() - 1;
                while (start < end) {
                    int tmp = levelNodes.get(start).val;
                    levelNodes.get(start).val = levelNodes.get(end).val;
                    levelNodes.get(end).val = tmp;
                    start++;
                    end--;
                }
            }
    
            depth++;
        }
    
        return rootNode;
    }
}

In the provided Java solution, the code defines functionality to reverse the values of nodes at odd levels in a binary tree using a breadth-first search (BFS) approach.

• Begin by testing the root node for nullity. If the rootNode is null, return null immediately as there's no tree to process.
• Initialize a Queue<TreeNode> which aids in implementing BFS to iterate through tree levels. Enqueue the rootNode to start the BFS.
• Utilize a depth counter initialized to zero to keep track of the current tree level.
• Employ a while loop that continues as long as there are nodes in the queue. This loop handles one tree level per iteration.
• At each iteration:
  • Determine the number of nodes (count) at the current level by checking the queue size.
  • Use an ArrayList<TreeNode> to store the nodes of the current level.
  • For each node in the current level:
    • Dequeue the node and add it to levelNodes.
    • Enqueue the node's left and right children (if they exist) for processing in subsequent levels.
  • After all nodes at the current level are processed, check if the current depth is odd (using modulus operation):
    • If odd, reverse the node values in levelNodes by swapping elements symmetrically from the exterior toward the center using two-pointer technique.
• Increment the depth counter after processing each level.
• Finally, return the modified rootNode, which now reflects the changes applied to its odd levels after all iterations.

This method makes effective use of BFS to traverse the tree level-by-level, and array data manipulation for reversing operations, ensuring correct handling of all scenarios dictated by the tree structure.

class Solution:
    def reverseOddLevels(self, tree_root):
        if not tree_root:
            return None
    
        bfs_queue = [tree_root]  # Initialize queue with root
        tree_level = 0
    
        while bfs_queue:
            level_length = len(bfs_queue)
            nodes_this_level = []
    
            for _ in range(level_length):
                node = bfs_queue.pop(0)
                nodes_this_level.append(node)
    
                if node.left:
                    bfs_queue.append(node.left)
                if node.right:
                    bfs_queue.append(node.right)
    
            if tree_level % 2 == 1:
                start, end = 0, len(nodes_this_level) - 1
                while start < end:
                    # Swap values between start and end
                    nodes_this_level[start].val, nodes_this_level[end].val = nodes_this_level[end].val, nodes_this_level[start].val
                    start += 1
                    end -= 1
    
            tree_level += 1
    
        return tree_root  # Modified tree root is returned.

The given Python code provides a solution to the problem of reversing the values at odd levels in a binary tree. It uses Breadth-First Search (BFS) to navigate through the tree and performs the reversal of values at every odd level found.

Here's how the code works:

1. Check if the input tree root is empty (None). If it is, return None.
2. Initialize a queue (bfs_queue) to manage node traversal, starting with the tree root.
3. Use a variable (tree_level) to track the current level in the tree, initialized at 0 (the root level).
4. Initiate a loop that continues as long as there are nodes in the queue:
   • Determine the number of nodes at the current level by checking the length of the queue.
   • Create an empty list (nodes_this_level) to hold the nodes present at the current level.
   • Extract nodes from the queue for the entire current level (based on the earlier determined size), and add them to nodes_this_level. Simultaneously, add their child nodes (if any) to the queue for further processing.
   • If the current level is odd (i.e., tree_level % 2 == 1), reverse the node values at this level:
     • Initialize two pointers, start and end, to the first and last indices of the nodes_this_level list, respectively.
     • Swap the values at these pointers and move towards the center of the list until all nodes at that level have been processed.
   • Increment tree_level by 1 to move to the next level.
5. Finally, return the modified root of the tree, which now has reversed values on its odd levels.

In summary, the solution efficiently traverses the tree level by level, reversing nodes' values at each odd level without modifying the tree structure, thus ensuring that the operations conform to the expected tree operations in breadth-first manner.