Skip to content
GKgkml.dev
← Problem set
#226EasyTrees & BST

Invert Binary Tree

The tell: A structural transformation that applies identically to every subtree.

How you get there

  1. 1Swap the two children at the current node.
  2. 2Recurse into both — the operation is self-similar.
  3. 3The base case is an empty node, which needs nothing done.

Solution

Python
def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root
Time
O(n)
Space
O(h)

What goes wrong

Assigning left before computing the new right uses the already-overwritten value in some phrasings.

Test yourself on DSANext: Kth Smallest Element in a BST →