How do you solve Invert Binary Tree on LeetCode?

Invert Binary Tree (LeetCode #226) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Inverting a binary tree is a simple swap operation at each node.

What is the brute force solution for Invert Binary Tree?

The brute force approach for Invert Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves traversing the tree and swapping the left and right children of each node. This is straightforward but inefficient as it may require multiple passes over the tree. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Invert Binary Tree?

Invert Binary Tree uses the following concepts: Tree, Depth-First Search, Breadth-First Search, Binary Tree. The recommended patterns to study are: Depth-First Search, Recursion.

What are the interview tips for Invert Binary Tree?

Always clarify the problem and ask about edge cases (like an empty tree). Think about both iterative and recursive approaches, as interviewers may ask for both. Practice explaining your thought process clearly while coding.

What are common mistakes when solving Invert Binary Tree?

Not handling the null case properly, which can lead to null pointer exceptions. Confusing left and right children during the swap.

#226

Invert Binary Tree

Easy

TreeDepth-First SearchBreadth-First SearchBinary TreeDepth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach uses a recursive depth-first search (DFS) to invert the tree in a single pass. This is efficient as it only requires visiting each node once.

⚙️

Algorithm

3 steps

1Step 1: If the current node is null, return.
2Step 2: Swap the left and right children of the current node.
3Step 3: Recursively call the function on the left and right children.

solution.py13 lines

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7def invertTree(root):
8    if not root:
9        return root
10    root.left, root.right = root.right, root.left
11    invertTree(root.left)
12    invertTree(root.right)
13    return root

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.

1Inverting a binary tree is a simple swap operation at each node.
2Recursion can simplify tree traversal problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.