Bird
Raised Fist0
Interview Preptree-dfseasyGoogleAmazonFacebook

Invert Binary Tree

Choose your preparation mode4 modes available
📋
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
}
0/10
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
t1_01basic
Input{"root":[4,2,7,1,3,6,9]}
Expected[4,7,2,9,6,3,1]

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.

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

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

t2_01edge
Input{"root":null}
Expectednull

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

t2_02edge
Input{"root":[1]}
Expected[1]

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

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

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

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

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

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

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

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]

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

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

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

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]}
⏱ 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.

Practice

(1/5)
1. You need to place the minimum number of cameras in a binary tree so that every node is monitored. A camera at a node monitors its parent, itself, and its immediate children. Which approach guarantees an optimal solution for this problem?
easy
A. Brute force recursion trying all combinations of camera placements
B. Greedy postorder traversal using explicit states to track coverage and camera placement
C. Top-down dynamic programming with memoization based on node coverage
D. Level order traversal placing cameras on all nodes with uncovered children

Solution

  1. Step 1: Understand problem constraints

    The problem requires minimal cameras covering all nodes, where a camera covers parent, self, and children.
  2. Step 2: Evaluate approaches

    Brute force is exponential and inefficient. Level order placing cameras on all uncovered children is greedy but not minimal. Top-down DP is complex and less intuitive here. Greedy postorder with explicit states ensures children are processed before parent decisions, enabling minimal camera placement.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Postorder traversal with states is known optimal for this problem [OK]
Hint: Optimal solution uses postorder traversal with states [OK]
Common Mistakes:
  • Assuming level order greedy placement is minimal
  • Trying brute force without pruning
  • Confusing top-down DP with bottom-up greedy
2. Given a binary tree, you need to find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. Which approach guarantees an optimal solution to this problem?
easy
A. Perform a postorder traversal computing heights and update the diameter at each node using recursion with a global variable.
B. Apply dynamic programming with memoization on node pairs to find longest paths.
C. Use a greedy traversal that always chooses the deeper subtree at each node.
D. Calculate the height of the tree and multiply by two to estimate the diameter.

Solution

  1. Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.

    The diameter can be found by checking the sum of left and right subtree heights at every node.
  2. Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.

    This approach visits each node once, updating the diameter with left_height + right_height.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Postorder traversal with global diameter update covers all nodes [OK]
Hint: Diameter updates at every node, not just root [OK]
Common Mistakes:
  • Thinking diameter must pass through root
  • Using greedy to pick deeper subtree only
  • Confusing diameter with twice height
3. Given a binary tree where each root-to-leaf path represents a number formed by concatenating node values, which algorithmic approach guarantees computing the sum of all such numbers efficiently without missing any path or double counting partial paths?
easy
A. Depth-first search (DFS) that accumulates the current number along the path and adds it only at leaf nodes
B. Dynamic programming that stores sums for subtrees and combines them at the root
C. Greedy traversal that sums node values at each level independently
D. Breadth-first search (BFS) that sums values of nodes at each depth and multiplies by depth

Solution

  1. Step 1: Understand problem requirements

    The problem requires summing numbers formed by concatenating node values from root to leaf, so partial paths must not be summed prematurely.
  2. Step 2: Identify correct traversal pattern

    DFS naturally explores root-to-leaf paths, allowing accumulation of the current number and summing only at leaf nodes, ensuring correctness.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DFS accumulates path values correctly and sums only at leaves [OK]
Hint: Sum only at leaves during DFS traversal [OK]
Common Mistakes:
  • Summing at non-leaf nodes
  • Using BFS without path tracking
4. The following code attempts to check if a binary tree is balanced using iterative postorder traversal. Which line contains a subtle bug that can cause incorrect results on an empty tree or null root?
medium
A. Line 1: Missing check for empty root before traversal
B. Line 7: Incorrectly pushing node.left without null check
C. Line 12: Comparing last_visited with peek.right incorrectly
D. Line 16: Using abs difference without considering null children

Solution

  1. Step 1: Identify handling of empty tree

    The code does not check if root is None before starting traversal, which can cause errors or incorrect results.
  2. Step 2: Verify other lines

    Other lines handle null children safely using heights.get with default 0, and last_visited logic is correct.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing early return for empty root causes bug [OK]
Hint: Always check for empty root before traversal [OK]
Common Mistakes:
  • Forgetting to handle empty tree as balanced
  • Incorrectly comparing last_visited causing infinite loops
  • Not defaulting heights for null children
5. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?
medium
A. Line creating root node with postorder[-1]
B. Line initializing inorder_index to 0
C. Line attaching node as right child
D. Line popping from stack inside while loop

Solution

  1. Step 1: Identify inorder_index initialization

    inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.
  2. Step 2: Consequences of wrong initialization

    Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Correct inorder_index initialization is critical for stack popping logic [OK]
Hint: inorder_index must start at last index, not zero [OK]
Common Mistakes:
  • Wrong inorder_index initialization
  • Confusing postorder traversal direction
  • Incorrect stack popping conditions
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard