How to Solve: Invert a Binary Tree – Complete Guide for FAANG Interviews

How to Solve: Invert a Binary Tree – Complete Guide for FAANG Interviews

? Introduction

"This problem is a litmus test for recursion and tree traversal—Google famously asked it in their interviews, and nailing it proves you can handle hierarchical data structures with clarity and efficiency."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Binary Tree Basics – Structure, nodes, left/right children, root. 2. Tree Traversal (DFS/BFS) – Depth-First Search (pre-order, in-order, post-order) and Breadth-First Search (level-order). 3. Recursion vs. Iteration – How to implement both for tree problems.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Follow this repeatable mental checklist for every binary tree inversion problem:

1. Clarify the Problem
2. Confirm input/output: Is it a binary tree? Should we return the root or modify in-place?

3. Ask: "Can the tree be empty? Can it have only one child?"

4. Choose a Traversal Strategy

5. Recursive DFS (Post-Order): Best for simplicity and clarity.
6. Iterative BFS: Best for level-order processing or avoiding recursion limits.

7. Iterative DFS: Best for deep trees where recursion might stack overflow.

8. Base Case Handling

9. If root == null, return null (or do nothing if in-place).

10. If root.left == null && root.right == null, return root (no inversion needed).

11. Swap Children

12. For the current node, swap left and right children.

13. Example: root.left, root.right = root.right, root.left

14. Recurse or Iterate

15. Recursive: Call inversion on left and right subtrees.

16. Iterative: Use a queue/stack to process nodes level by level.

17. Edge Case Testing

18. Test with:

    • Empty tree (null).
    • Single-node tree.
    • Skewed tree (all left or all right children).
    • Full binary tree (all nodes have 2 children).

19. Time & Space Complexity

20. Time: O(N) (visit every node once).
21. Space:
    • Recursive: O(H) (height of tree, worst-case O(N) for skewed tree).
    • Iterative: O(N) (queue/stack storage).

? WORKED EXAMPLES

Example 1 – Basic (Recursive DFS)

Problem: Invert a binary tree recursively.

Thought Process: 1. Base case: If root is null, return null. 2. Swap left and right children. 3. Recursively invert left and right subtrees.

Python Code:

class TreeNode:

    def __init__(self, val=0, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

def invertTree(root):

    if not root:

        return None

    # Swap left and right children

    root.left, root.right = root.right, root.left

    # Recursively invert subtrees

    invertTree(root.left)

    invertTree(root.right)

    return root

Time Complexity: O(N) (visit every node once). Space Complexity: O(H) (recursion stack, where H is tree height).

Why This Works: - Post-order traversal ensures children are processed before the parent, so swapping happens from the bottom up.

Example 2 – Medium (Iterative BFS)

Problem: Invert a binary tree iteratively using BFS.

Thought Process: 1. Use a queue to process nodes level by level. 2. For each node, swap its left and right children. 3. Enqueue the children for further processing.

Python Code:

from collections import deque

def invertTree(root):

    if not root:

        return None

    queue = deque([root])

    while queue:

        node = queue.popleft()

        # Swap left and right children

        node.left, node.right = node.right, node.left

        # Enqueue children if they exist

        if node.left:

            queue.append(node.left)

        if node.right:

            queue.append(node.right)

    return root

Time Complexity: O(N) (visit every node once). Space Complexity: O(N) (queue storage, worst-case for a full tree).

Why This Works: - BFS processes nodes level by level, ensuring all children are swapped before moving to the next level.

Example 3 – Hard/Follow-Up (Iterative DFS with Stack)

Problem: Invert a binary tree iteratively using DFS (post-order simulation).

Thought Process: 1. Use a stack to simulate post-order traversal. 2. Push nodes onto the stack, then process them in reverse order (children before parent). 3. Swap children when popping from the stack.

Python Code:

def invertTree(root):

    if not root:

        return None

    stack = [root]

    while stack:

        node = stack.pop()

        # Swap left and right children

        node.left, node.right = node.right, node.left

        # Push children onto the stack (right first, then left)

        if node.right:

            stack.append(node.right)

        if node.left:

            stack.append(node.left)

    return root

Time Complexity: O(N) (visit every node once). Space Complexity: O(N) (stack storage, worst-case for skewed tree).

Why This Works: - The stack ensures we process nodes in a way that mimics post-order traversal, swapping children before their parent.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Inverting a binary tree is all about traversal and swapping. Here’s the playbook:

1. Pick your traversal: Recursive DFS is simplest, BFS is great for levels, and iterative DFS avoids recursion limits.
2. Base case first: If the node is null, return null.
3. Swap children: left and right get swapped at every node.
4. Recurse or iterate: Process children before or after swapping, depending on your method.
5. Test edge cases: Empty tree, single node, skewed tree—don’t skip these!

Time complexity is always O(N), space depends on your method. Recursive is O(H), iterative is O(N).

Now go crush that interview—you’ve got this!

Final Notes

• Practice Variations: Try inverting a tree where nodes have parent pointers, or inverting only certain levels.
• Whiteboard Tip: Draw the tree before and after inversion to visualize the swaps.
• Follow-Up Questions: Be ready for "What if the tree is a BST?" (Inversion breaks BST properties unless you adjust values).

This guide is 100% interview-ready—every line is actionable under pressure. Good luck! ?