Command Palette

Search for a command to run...

Hectal
Problem 16.2 · Binary TreesEasy

Invert Binary Tree

PatternTree DFS

What it teaches: Changing a tree's structure recursively: swap the children of every node.

Practise it on judges as “Invert Binary Tree”.

The problem

Mirror a binary tree (swap every node's left and right subtrees) and return its root.

Example 1

Input: root = [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]

Constraints

  • 0 ≤ nodes ≤ 100

Pattern clues in the wording

  • → Same operation at every node

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public TreeNode invertTree(TreeNode root) {
        return root;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
root = [4,2,7,1,3,6,9]
[4,7,2,9,6,3,1]
2
root = [2,1,3]
[2,3,1]
3
root = []
[]

From slow to fast

Approaches

1. Recursive swap · O(n)
1

Recursive swap

Time O(n) Space O(h)

For each node, invert both subtrees and swap them.

▶ Dry run: Mirroringroot = [4, 2, 7, 1, 3, 6, 9]
1234679

Step 1/3Start at the root 4.

Approach 1
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

Verdict: One visit per node.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Empty tree
  • One child only

Mistakes people make

  • Overwriting root.left before saving it.

Interview

Follow-up questions

Can you do it iteratively?