DSA With AI
Week 4 ยท Trees

Invert Binary Tree

Mirror a binary tree by swapping every node's left and right subtrees. The important move is applying the swap recursively, not just at the root.

Easy Trees Week 4 Practice runner

Frame the problem

  • The input may be empty.
  • Every node must keep its value.
  • The output tree has the same nodes and shape mirrored left-to-right.
1. Reveal example inputs and outputs

Example 1

Input:

invert_tree([
  4,
  [
    2,
    [
      1,
      null,
      null
    ],
    [
      3,
      null,
      null
    ]
  ],
  [
    7,
    [
      6,
      null,
      null
    ],
    [
      9,
      null,
      null
    ]
  ]
])

Output:

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

Example 2

Input:

invert_tree([
  1,
  null,
  null
])

Output:

[
  1,
  null,
  null
]
2. Brute force first

If you drew the tree on paper, which local operation would you repeat at each node?

3. Reveal the insight ladder
  1. An empty subtree is already inverted.
  2. A leaf is unchanged after swapping two empty children.
  3. For a non-empty node, invert the right subtree into the new left and the left subtree into the new right.
  4. The same recursive rule works for every node.
4. Dry run before code
  1. Root 4 has children 2 and 7.
  2. After inversion, 7 becomes the left child and 2 becomes the right child.
  3. The subtree rooted at 7 also swaps 6 and 9.
  4. The subtree rooted at 2 swaps 1 and 3.
5. Reveal final Python solution 
def invert_tree(root):
    if root is None:
        return None
    value, left, right = root
    return [value, invert_tree(right), invert_tree(left)]

Complexity: Time O(n), because every node is visited once. Space O(h) from the recursion stack.

Interview narration

  • I will define the recursive contract as returning the inverted version of this subtree.
  • The base case is the empty tree.
  • The recursive step swaps the already-inverted child results.

Common traps

  • Swapping only the root's children.
  • Destructuring None before checking the base case.
  • Forgetting that in-place TreeNode solutions should return the original root pointer after swaps.

Follow-up drills

1. How would the in-place TreeNode version differ?

You would swap node.left and node.right on the existing object, then recurse into the two children. The return value is still the same root object.

2. Can you solve it iteratively?

Yes. Use a stack or queue of nodes. Pop a node, swap its children, and push any non-empty children until the worklist is empty.

3. What tree shape creates the worst recursion depth?

A completely skewed tree creates recursion depth O(n), which can hit Python recursion limits for very large inputs.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.