Invert Binary Tree

📋

Problem

Imagine you have a family tree diagram and want to see it flipped horizontally, like looking at it in a mirror. This problem asks you to invert a binary tree in a similar way.

Given the root of a binary tree, invert the tree, and return its root. Inverting a binary tree means swapping the left and right children of all nodes in the tree.

The number of nodes in the tree is in the range [1, 10^5].Node values can be any integer.The tree can be unbalanced.

Edge cases: Single node tree → output is the same single nodeTree with only left children → output is a tree with only right childrenTree with only right children → output is a tree with only left children

</>

IDE

def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:public TreeNode invertTree(TreeNode root)TreeNode* invertTree(TreeNode* root)function invertTree(root)

def invertTree(root):
    # Write your solution here
    pass

class Solution {
    public TreeNode invertTree(TreeNode root) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

TreeNode* invertTree(TreeNode* root) {
    // Write your solution here
    return nullptr;
}

function invertTree(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Original tree unchangedForgot to swap left and right children at each node.✅ Add code to swap root.left and root.right after recursive inversion calls.

Wrong: Partial inversion only at root levelSwapped children only at root, not recursively for subtrees.✅ Apply inversion recursively to left and right subtrees before swapping.

Wrong: Null pointer exceptions or crashes on empty inputNo base case for null root in recursion.✅ Add base case: if root is None, return None immediately.

Wrong: Incorrect structure for skewed treesSwapping logic does not handle null children properly.✅ Always swap left and right pointers regardless of null children.

Wrong: Time limit exceeded on large inputsInefficient algorithm with exponential or repeated work.✅ Use O(n) DFS or BFS traversal with in-place swapping.

✓

Test Cases

Try testing your code on empty and single-node trees to handle base cases.

Test your code on unbalanced trees and trees with missing children to catch corner cases.

Optimize your recursive solution to run efficiently on large trees.

t1_01basic

Input{"root":[4,2,7,1,3,6,9]}

Expected[4,7,2,9,6,3,1]

⏱ Performance - must finish in 2000ms

The original tree has root 4 with left child 2 and right child 7. After inversion, 2 and 7 are swapped, and this swapping continues recursively for all nodes.

💡 Think about swapping left and right children at every node.

💡 Use a postorder traversal to invert subtrees before swapping.

💡 Recursively invert left and right subtrees, then swap them.

Why it failed: Failed to invert children recursively or forgot to swap left and right pointers at each node. Fix by ensuring postorder traversal and swapping root.left and root.right after recursive calls.

✓ Correctly inverts the tree by recursively swapping children.

t1_02basic

Input{"root":[1,2,3,4,5,6,7]}

Expected[1,3,2,7,6,5,4]

⏱ Performance - must finish in 2000ms

A complete binary tree with root 1 and children 2 and 3. After inversion, left and right children are swapped at every node.

💡 Visualize the tree and its mirror image.

💡 Check that each node's left and right children are swapped recursively.

💡 Implement recursive calls on left and right subtrees before swapping.

Why it failed: Output does not reflect swapped children at all levels. Likely missed recursive inversion or swapping step. Fix by applying inversion recursively and swapping children at each node.

✓ Successfully inverts the tree structure recursively.

t2_01edge

Input{"root":null}

Expectednull

⏱ Performance - must finish in 2000ms

Empty tree input should return null as there is nothing to invert.

💡 Check if the root is null before processing.

💡 Return null immediately if the tree is empty.

💡 Add a base case in recursion to handle null root.

Why it failed: Function crashes or returns non-null for empty input. Fix by adding base case: if root is None, return None immediately.

✓ Correctly handles empty tree by returning null.

t2_02edge

Input{"root":[1]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node tree remains the same after inversion since no children to swap.

💡 Consider what happens when a node has no children.

💡 Inversion of a leaf node should return the node itself.

💡 Ensure recursion handles leaf nodes without error.

Why it failed: Output changes single node or causes error. Fix by returning node as is when both children are null.

✓ Correctly returns single node tree unchanged.

t2_03edge

Input{"root":[1,2,null,3,null,null,null]}

Expected[1,null,2,null,3]

⏱ Performance - must finish in 2000ms

Tree with only left children becomes a tree with only right children after inversion.

💡 Check how inversion affects skewed trees.

💡 Left children become right children after inversion.

💡 Verify recursive swapping even when one child is null.

Why it failed: Output does not reflect correct swapping of left-only children to right-only. Fix by swapping children even if one is null.

✓ Correctly inverts left-skewed tree to right-skewed.

t2_04edge

Input{"root":[1,null,2,null,3]}

Expected[1,2,null,3]

⏱ Performance - must finish in 2000ms

Tree with only right children becomes a tree with only left children after inversion.

💡 Consider the mirror effect on right-skewed trees.

💡 Right children become left children after inversion.

💡 Ensure swapping logic handles null left children correctly.

Why it failed: Output does not invert right-only children to left-only. Fix by swapping children pointers regardless of nulls.

✓ Correctly inverts right-skewed tree to left-skewed.

t3_01corner

Input{"root":[1,2,3,4,null,null,5]}

Expected[1,3,2,5,null,null,4]

⏱ Performance - must finish in 2000ms

Tree where some nodes have only one child; tests correct swapping even with missing children.

💡 Check that swapping occurs even if one child is null.

💡 Recursive calls must handle null children gracefully.

💡 Swap left and right pointers after recursive inversion of children.

Why it failed: Fails to swap children when one child is null, causing incorrect structure. Fix by always swapping left and right pointers after recursive calls regardless of nulls.

✓ Correctly handles nodes with single children during inversion.

t3_02corner

Input{"root":[1,2,3,4,5,6,7,8,9,10,11]}

Expected[1,3,2,7,6,5,4,11,10,9,8]

⏱ Performance - must finish in 2000ms

Complete binary tree with multiple levels; tests correct recursive inversion at all depths.

💡 Verify inversion at deeper levels of the tree.

💡 Ensure recursion reaches leaf nodes and swaps correctly on return.

💡 Use postorder traversal to invert subtrees before swapping.

Why it failed: Incorrect output due to incomplete recursion or swapping at deeper levels. Fix by ensuring full postorder traversal and swapping at every node.

✓ Successfully inverts multi-level complete binary tree.

t3_03corner

Input{"root":[1,2,3,4,null,null,5,null,6]}

Expected[1,3,2,5,null,null,4,6]

⏱ Performance - must finish in 2000ms

Tree with mixed null children and unbalanced shape; tests robustness of inversion logic.

💡 Check handling of unbalanced trees with missing children.

💡 Ensure swapping is done even if children are missing.

💡 Recursively invert subtrees before swapping pointers.

Why it failed: Fails on unbalanced trees with missing children due to null pointer errors or skipped swaps. Fix by adding null checks and always swapping children after recursion.

✓ Correctly inverts unbalanced tree with missing children.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced binary tree with 100 nodes to test performance. Algorithm must run in O(n) time within 2 seconds.

💡 Use O(n) time complexity algorithms like DFS or BFS.

💡 Avoid repeated work or unnecessary data structures.

💡 Recursive postorder traversal with in-place swapping is optimal.

Why it failed: Algorithm exceeds time limit due to exponential or inefficient complexity. Fix by using O(n) traversal and in-place swaps without extra overhead.

✓ Algorithm runs efficiently in O(n) time for large input.

Practice

1. You are given a binary tree and need to determine if it is a mirror of itself (i.e., symmetric around its center). Which approach guarantees an optimal solution that efficiently checks this property by comparing nodes in a mirrored fashion?

easy

A. Use a recursive DFS that simultaneously compares the left subtree of one node with the right subtree of the other node, returning false immediately on mismatch.

B. Perform a level-order traversal and compare nodes at each level from left to right.

C. Traverse the tree in preorder and check if the sequence of node values is a palindrome.

D. Use a brute force approach that generates all subtree permutations and checks for symmetry.

Solution

1. Step 1: Understand the problem requires mirrored subtree comparison

   The problem asks if the tree is symmetric, meaning the left subtree is a mirror reflection of the right subtree.

2. Step 2: Identify the approach that compares mirrored nodes recursively with early exit

   The recursive DFS approach compares left subtree nodes with right subtree nodes in mirrored positions and returns false immediately if any mismatch is found, ensuring efficiency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mirrored recursive DFS matches problem requirements [OK]

Hint: Symmetry requires mirrored subtree comparison [OK]

Common Mistakes:

• Assuming preorder traversal palindrome check works
• Using level-order traversal without mirrored comparison
• Trying brute force subtree permutations

2. Consider this buggy iterative postorder traversal code:

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited == peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

What is the bug in this code?

medium

A. The inner while loop should traverse right children instead of left

B. The condition should check if last_visited != peek_node.right, not == peek_node.right

C. The last_visited variable is never updated

D. The result list is appended before traversing the left subtree

Solution

1. Step 1: Examine condition for traversing right subtree

   Correct logic requires moving to right child if it exists and was not visited yet, so condition must be last_visited != peek_node.right.

2. Step 2: Identify effect of wrong condition

   Using last_visited == peek_node.right causes skipping right subtree traversal or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing condition restores correct postorder traversal [OK]

Hint: Check last_visited != right child to avoid revisiting [OK]

Common Mistakes:

• Using == instead of !=
• Not updating last_visited
• Appending too early

3. What is the time complexity of the BFS-based algorithm to compute the maximum depth of a binary tree with n nodes, and why might the following common misconception be incorrect? Options:

medium

A. O(n), but with O(n) auxiliary space for the queue at the widest level

B. O(n), because each node is visited exactly once in BFS

C. O(n log n), because each level requires sorting nodes

D. O(n^2), because each node is enqueued and dequeued multiple times

Solution

1. Step 1: Identify time complexity

   BFS visits each node exactly once, so time complexity is O(n).

2. Step 2: Identify space complexity and common misconception

   Queue can hold up to O(n) nodes at the widest level, so auxiliary space is O(n). The misconception is thinking nodes are processed multiple times, leading to O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each node enqueued and dequeued once; max queue size O(n) [OK]

Hint: BFS visits each node once; space depends on max level width [OK]

Common Mistakes:

• Assuming multiple visits per node
• Confusing sorting with traversal
• Ignoring queue space usage

4. If the binary tree nodes can have parent pointers in addition to left and right children, which modification to the iterative one-stack postorder traversal algorithm can eliminate the need for the last_visited variable?

hard

A. Use the parent pointer to move back up after visiting a node's children, tracking traversal direction

B. Push nodes twice onto the stack to simulate postorder without tracking last visited

C. Perform a preorder traversal and reverse the output list at the end

D. Use two stacks: one for traversal and one for output, ignoring parent pointers

Solution

1. Step 1: Understand role of last_visited

   Last_visited tracks if right child was processed to avoid revisiting; parent pointers can provide traversal direction.

2. Step 2: Use parent pointer to detect traversal direction

   By moving up via parent pointer, algorithm knows if coming from left or right child, eliminating need for last_visited.

3. Step 3: Compare other options

   Options B and D ignore parent pointers; A reverses preorder but does not leverage parent pointers; C uses parent pointers effectively.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Parent pointers enable direction-aware traversal without extra state [OK]

Hint: Parent pointers track traversal direction, removing last_visited [OK]

Common Mistakes:

• Ignoring parent pointers
• Using two stacks unnecessarily
• Reversing preorder output without parent info

5. Suppose the binary tree nodes can have an arbitrary number of children (not just two). Which modification to the BFS-based maximum depth algorithm correctly computes the maximum depth in this scenario?

hard

A. Replace 'if node.left' and 'if node.right' checks with iterating over 'node.children' list and enqueue each child.

B. Keep the same code but only enqueue 'node.left' and 'node.right' if they exist, ignoring other children.

C. Use DFS recursion only, as BFS cannot handle nodes with more than two children.

D. Modify the code to sum depths of all children instead of taking the maximum.

Solution

1. Step 1: Understand the problem extension

   Nodes now have arbitrary children, so left/right pointers are insufficient.

2. Step 2: Modify BFS to handle multiple children

   Iterate over 'node.children' list and enqueue each child to explore all branches correctly.

3. Step 3: Evaluate other options

   Ignoring children misses nodes; DFS can work but BFS is still valid; summing depths is incorrect for max depth.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Enqueue all children ensures full traversal for max depth [OK]

Hint: Enqueue all children nodes to handle arbitrary branching [OK]

Common Mistakes:

• Ignoring extra children
• Assuming binary tree structure
• Summing depths instead of max