Invert Binary Tree – 226. LeetCode

Imagine you are looking at a family tree. If you flip it horizontally, the left children become right children and the right children become left children. This is exactly what the Invert Binary Tree problem asks us to do: swap all the left and right children of every node in a binary tree.

In non-technical terms, this is like creating a “mirror image” of a binary tree.

Recursive Solution

Advantages:

1. Simple and Clean: Recursion often leads to shorter and cleaner code, especially for problems involving trees or divide-and-conquer.

2. Natural Fit for Trees: Recursive logic matches the hierarchical structure of trees, making traversal easy to implement.

3. Less Boilerplate Code: You don’t need to manage explicit data structures like stacks or queues.

Disadvantages:

1. Stack Overflow Risk: Deep recursion can exceed the system’s call stack limit, causing a stack overflow error (e.g., for skewed trees).

2. Extra Space: Recursive calls use additional memory on the call stack, leading to O(H) space complexity, where H is the height of the tree.

3. Harder to Debug: It can be challenging to debug recursive code because the call stack grows and shrinks dynamically.

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class InvertBinaryTree {
    public TreeNode invertTree(TreeNode root) {
        // Base case: If the node is null, do nothing
        if (root == null) return null;

        // Swap the left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // Recursively invert left and right subtrees
        invertTree(root.left);
        invertTree(root.right);

        return root; // Return the modified root
    }
}

Line-By-Line Explanation

Step 1: Base Case

if (root == null) return null;
  • Base case is essential for recursion. Without it, the method would attempt to access null pointers.

Step 2: Swap Left and Right Children

TreeNode temp = root.left;
root.left = root.right;
root.right = temp;

• Swapping the left and right children is the core operation needed to “invert” the tree.

• By performing this swap at each node, the tree gradually becomes a mirror image of itself.

Step 3: Recursive Calls

invertTree(root.left);
invertTree(root.right);

• Since a binary tree has a hierarchical structure, recursion is a natural choice to process all nodes.

• The recursion traverses the tree in preorder (current node, left subtree, right subtree):

1. Swap the current node’s children.

2. Invert the left subtree.

3. Invert the right subtree.

Step 4: Return

return root;


• Ensures the method meets the requirement of returning the inverted tree structure.

Iterative Solution

1. Avoids Stack Overflow: By using an explicit stack or queue, the iterative approach can handle deep or large inputs without risking overflow.

2. Better Control: You have more control over the traversal process (e.g., DFS or BFS).

3. Easier Debugging: Debugging is more straightforward since you explicitly manage the flow of the program.

Disadvantages:

1. More Boilerplate Code: Iterative solutions require additional code to manage the stack or queue explicitly.

2. Harder to Write: It can be less intuitive to write iterative code, especially for problems naturally suited for recursion.

3. Memory Overhead: Explicit data structures (e.g., stacks or queues) can consume more memory in BFS or complex iterations.

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class InvertBinaryTree {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();

            // Swap left and right child
            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;

            // Push non-null children onto the stack
            if (current.right != null) stack.push(current.right);
            if (current.left != null) stack.push(current.left);
        }

        return root;
    }
}

Line-By-Line Explanation

Step 1: Handle Edge Case

if (root == null) return null;
  • Checks if the input tree is null. If yes, return null immediately.

Step 2: Initialize a Stack for DFS

Stack<TreeNode> stack = new Stack<>();
stack.push(root);

• Explicit stack usage avoids recursion depth issues (e.g., stack overflow for deep trees).

• DFS traversal is efficient for processing all nodes.

Step 3: Process Nodes in DFS Order

while (!stack.isEmpty()) {
    TreeNode current = stack.pop();

• Continues the process as long as there are nodes in the stack.

• Removes the top node (current node) from the stack for processing.
• This simulates the behavior of recursion, where nodes are processed one at a time.

Step 4: Swap Left and Right

TreeNode temp = current.left;
current.left = current.right;
current.right = temp;

• Swaps the left and right children of the current node:

• Stores the left child in a temporary variable.

• Assigns the right child to current.left.

• Assigns the temporary variable to current.right.

Step 5: Push Non-Null Children Onto Stack

if (current.right != null) stack.push(current.right);
if (current.left != null) stack.push(current.left);

• Pushing non-null children ensures all nodes are processed.

• The stack simulates the call stack in recursion, maintaining the DFS order.

Step 6: Return the Modified Tree

return root;


• Returning the root after modifications ensures the method aligns with the problem requirements.

Why Invert Binary Tree?


The “Invert Binary Tree” problem highlights the power of recursion for clean, intuitive solutions and iteration for handling deeper trees efficiently. Mastering both approaches strengthens your understanding of tree traversal and prepares you for more complex tree-based challenges in coding interviews.

Leave a Reply

Your email address will not be published. Required fields are marked *