Invert Binary Tree

class Solution {
    public TreeNode reverseTree(TreeNode rootNode) {
        if (rootNode == null) return null;
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        nodeQueue.add(rootNode);
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            TreeNode swapHolder = node.left;
            node.left = node.right;
            node.right = swapHolder;
            if (node.left != null) nodeQueue.add(node.left);
            if (node.right != null) nodeQueue.add(node.right);
        }
        return rootNode;
    }
}

The problem requires you to invert a binary tree, and the provided Java solution successfully achieves this using a breadth-first search approach. The solution defines a method reverseTree that accepts the root node of a binary tree and returns the root of the inverted tree.

Here's how the solution works:

1. Check if the input rootNode is null. If so, return null immediately, indicating there's nothing to invert.
2. Initialize a Queue to keep track of the tree nodes, ensuring each node and its children are processed in a level-order manner (breadth-first).
3. Add the rootNode to the queue as the starting point of the tree traversal.
4. Execute a loop as long as the queue is not empty. During each iteration of the loop:
   • Remove the front node from the queue using poll() and store it in a variable node.
   • Swap the left and right children of the current node.
   • Store the right child in a temporary variable swapHolder before the swap to facilitate easy swapping.
   • After swapping, if the left child of node is not null, add it to the queue to process its children in subsequent iterations.
   • Similarly, add the right child of node to the queue if it is not null.
5. After the loop completes, all nodes of the tree will have their children inverted, and the method returns the modified rootNode, now representing the root of the inverted tree.

This solution leverages a queue to ensure the tree is traversed level by level and swaps children of each node to invert the binary tree successfully. The reverseTree method modifies the tree in-place and returns the root of the newly inverted tree, ready for further operations or checks as needed.

class Solution:
    def flipTree(self, node: Optional[TreeNode]) -> Optional[TreeNode]:
        if node is None:
            return None

        nodes = collections.deque([node])
        while nodes:
            current_node = nodes.popleft()
            current_node.left, current_node.right = current_node.right, current_node.left

            if current_node.left:
                nodes.append(current_node.left)

            if current_node.right:
                nodes.append(current_node.right)

        return node

The given Python code defines a method to invert or flip a binary tree. The solution employs a breadth-first search approach using a queue to iterate through each node of the tree and swap its left and right children.

• Functional Explanation:

  • The method flipTree takes a node, which is the root of a binary tree.
  • Utilize a deque from Python's collections module to manage nodes in a breadth-first manner.
  • If the input node is None, immediately return None which handles the empty tree scenario.
  • For each node dequeued, swap its left and right children.
  • If children nodes exist, they are added to the queue to continue the inversion process iteratively until all nodes have been processed.
  • Finally, the original root node, now representing the root of the inverted tree, is returned.

• Key Operations:

  • Swapping the left and right children of each node.
  • Utilizing a queue to manage breadth-first traversal of the tree.

This implementation ensures that every node in the tree is visited once, achieving the inversion in linear time proportional to the number of nodes in the tree, making it efficient and effective for practical usage.