Flip Tree

Invert a binary tree: swap the left and right child of every node. Return the root.

flipTree(root)

Input format: level-order with x for missing children. Output the flipped tree in the same level-order format.

Examples

4 2 7 1 3 6 9   // → 4 7 2 9 6 3 1
1 2             // → 1 x 2
(empty)         // → (empty)

Walkthrough

Thinking it through

Inverting a tree means every node's left and right children trade places — at every node, not just the root, since each node's own children need mirroring too. That's a recursive, node-by-node operation: whatever fixes one node, apply the same fix to every node beneath it.

Building the approach

At a single node: swap left and right — hold the left child, set left to the current right, set right to what you held.

Swapping at the root alone doesn't finish the job — the subtrees hanging off the swapped children need their own children flipped too, all the way down. So after swapping a node's children, recurse into each and apply the same swap-then-recurse logic. The effect cascades to every node's local orientation, down to the leaves.

The base case: a missing node has nothing to swap and nothing to recurse into.

Why order doesn't matter here

Swapping before or after recursing makes no difference — the swap only touches this node's own two pointers, and the recursive calls only touch pointers strictly below. They never interfere. This independence — a local fix here doesn't affect a local fix elsewhere — is common in tree recursion and part of why "do the local thing, then recurse" is so reliable for tree problems.

Why this is efficient

Every node is visited once at constant cost (a pointer swap) — O(n) time. The only extra space is the recursion stack, growing only as deep as the tree is tall — O(h) space.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.