You’re interviewing for a software engineering role at a large technology company.
The interviewer presents a simplified yet realistic production scenario:
A backend system models decision trees, feature toggles, and routing rules using binary trees. In certain operational modes, such as failover handling, experimentation, or mirrored execution, the system needs to invert these trees.
Inverting the tree means swapping the left and right child of every node. This transformation is used to:
- simulate reverse decision paths
- mirror feature execution flows
- test symmetry in recursive systems
- validate traversal logic under structural changes
Although the task sounds simple, interviewers use this problem to evaluate:
- understanding of tree traversal
- comfort with recursion and base cases
- ability to reason about in-place transformations
This is a classic foundational problem frequently asked in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews, especially for junior to mid-level roles.
Your Task
Given the root of a binary tree, invert the tree and return its root.
Inversion means that for every node in the tree:
left child ↔ right child
The inversion must be applied to all nodes in the tree.
Input Format
root: the root node of a binary tree
Each node is defined as:
TreeNode { int val; TreeNode left; TreeNode right; }
Output Format
Return the root node of the inverted binary tree
Examples
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:
Input: 4
/ \
2 7
/ \ / \
1 3 6 9
Output: 4
/ \
7 2
/ \ / \
9 6 3 1
Example 3:
Input: root = [2,1,3]
Output: [2,3,1]