Course4all
Join us on telegram
Home/dsa/Trees/Invert Binary Tree

Invert Binary Tree

Master this topic with zero to advance depth.

Invert Binary Tree

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

Easy

Examples

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

Level I: Recursive DFS

Intuition

To invert a binary tree, we swap the left and right children of every node. This can be done recursively: swap children of the current node, then recurse into both subtrees.

⏱ O(N)💾 O(H)

Detailed Dry Run

root = [4,2,7] -> Swap(2,7) -> [4,7,2]. Recurse into subtrees.

java
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        return root;
    }
}
Approach 2

Level II: Iterative BFS (Queue)

Intuition

Process the tree level by level. Use a queue to store nodes. For each node, swap its children and add them to the queue if they exist.

⏱ O(N)💾 O(W)

Detailed Dry Run

Queue: [4]. Pop 4, swap(2,7), Queue: [7,2]. Pop 7, swap(6,9)...

java
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        return root;
    }
}
Approach 3

Level III: Iterative DFS (Stack)

Intuition

Similar to BFS, but use a stack. The order of traversal doesn't change the fact that every node's children need to be swapped.

Diagram

(1) Swap children of Root (2) Result after subtrees 4 4 / \ / \ 2 7 7 2 / \ / \ / \ / \ 1 3 6 9 9 6 3 1
⏱ O(N)💾 O(H)

Detailed Dry Run

Stack: [4]. Pop 4, swap(2,7), Push(2,7). Pop 7, swap(6,9)... mirrored tree.

java
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return root;
    }
}
← Previous QuestionFind the City With the Smallest Number of Neighbors at a Threshold Distance
Next Question →Maximum Depth of Binary Tree