Algorithm-Day39-Invert-Binary-Tree-lc-226

Posted on In , Views:

🧩 Problem Description

Given the root of a binary tree, invert the tree, and return its root.

Inverting a binary tree means swapping every left and right child recursively.

💬 Example

1
2
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

💡 Approach: Recursive DFS

We recursively invert left and right subtrees, then swap them.

🔢 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

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

        root.left = right;
        root.right = left;

        return root;
    }
}

💡 Approach: Iterative BFS (Queue)

You can also invert using level-order traversal with a queue.

🔢 Java Code (Iterative BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode curr = queue.poll();

            // Swap left and right
            TreeNode temp = curr.left;
            curr.left = curr.right;
            curr.right = temp;

            if (curr.left != null) queue.offer(curr.left);
            if (curr.right != null) queue.offer(curr.right);
        }

        return root;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — visit every node once
  • Space Complexity:
    • Recursive: O(h) (call stack)
    • Iterative: O(w) (queue width)

✍️ Summary

  • Simple yet classic recursion problem.
  • Test your understanding of binary tree traversal.
  • Also seen in real-world scenarios like image mirror effects.