Invert Binary Tree
Mirror-flip a binary tree so every left subtree swaps with the right subtree. The quintessential problem for mastering tree recursion and depth-first traversal.
Problem Statement
Given the root of a binary tree, invert the tree, and return its root.
Examples & Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Depth-First Search (Recursive Swap)
Optimal ApproachRecursively swap the left and right children for every node down to leaf nodes.
Every node in the tree of size N is visited exactly once.
Consumes memory proportional to the height of the tree H on the recursion call stack (O(log n) for balanced tree, O(n) for skewed tree).
Underlying algorithmic logic
The Core Mental Model: The Mirror Reflection
Imagine standing in front of a mirror: your left hand appears on the right side, and your right hand appears on the left side.
At any node in a binary tree:
- Swap your left child pointer and your right child pointer.
- Tell your new left child to mirror itself recursively.
- Tell your new right child to mirror itself recursively.
The Recursive Contract
Because a binary tree is self-similar (every subtree is itself a complete binary tree), a function that successfully inverts one node can invert the entire tree:
- Base Case: If
root == null, there are no children to swap -> returnnull. - Recursive Step:
temp = root.left root.left = invertTree(root.right) root.right = invertTree(temp) return root
Every single node is visited and swapped exactly once, making the algorithm an optimal `O(n)` time operation. Memory is bounded strictly by the height of the tree O(h) on the call stack.
Step-by-step execution walkthrough
Swap left child (2) with right child (7).
Recursively invert node 7: swap child 6 and 9 to become 9 and 6.
Recursively invert node 2: swap child 1 and 3 to become 3 and 1.
- •Optimal O(n) runtime
- •Clean, concise recursive structure
- •Recursion depth bounded by tree height
Code Implementations
Ready-to-useCopy & paste production-ready solutions for Depth-First Search (Recursive Swap) in your language of choice
from __future__ import annotations# Definition for a binary tree node.class TreeNode:def __init__(self, val: int = 0, left: TreeNode | None = None, right: TreeNode | None = None):self.val = valself.left = leftself.right = rightdef invert_tree(root: TreeNode | None) -> TreeNode | None:if not root:return Noneroot.left, root.right = invert_tree(root.right), invert_tree(root.left)return rootdef print_in_order(root: TreeNode | None) -> str:result: list[int] = []def traverse(node: TreeNode | None) -> None:if not node:returntraverse(node.left)result.append(node.val)traverse(node.right)traverse(root)return " ".join(map(str, result))if __name__ == "__main__":root = TreeNode(4,TreeNode(2, TreeNode(1), TreeNode(3)),TreeNode(7, TreeNode(6), TreeNode(9)))print("In-order before inversion:", print_in_order(root))invert_tree(root)print("In-order after inversion: ", print_in_order(root))
Struggling to visualize how Binary Search Tree operates?
Watch pointers move, arrays shift, and recursion stacks unwind in real time. Step through custom inputs before writing code.
Frequently Asked Questions
Practice Similar Algorithmic Patterns
Reverse Linked List
Reverse the directional arrows of a singly linked list in-place. The classic test of reference manipulation and memory pointer management.
Binary Search
Locate a target value in a sorted array in O(log n) logarithmic time. Like opening a dictionary in the middle, each comparison eliminates half the remaining items.
Maximum Depth of Binary Tree
Find the maximum depth (height) of a binary tree along the longest path from root to leaf. The quintessential problem for learning bottom-up divide-and-conquer tree recursion.