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 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.

Invert Binary Tree — LeetCode #226 (Easy)

Tags: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Related patterns: Depth-First Search, Recursion

Brute Force approach

Time complexity: O(n²). Space complexity: O(1).

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 time complexity is O(n²) because for each node, we may end up traversing the entire tree again in a worst-case scenario. The space complexity is O(1) since we are not using any additional data structures.

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

1. Start at root (4). Swap left (2) and right (7). Now root = [4, 7, 2]. 2. Move to left child (7). Swap left (null) and right (9). Now node = [7, null, 9]. 3. Move to right child (9). Swap left (null) and right (null). No change. 4. Move back to root and go to right child (2). Swap left (1) and right (3). Now node = [2, 3, 1]. 5. Move to left child (3). Swap left (null) and right (null). No change. 6. Move to right child (1). Swap left (null) and right (null). No change.

Optimal Solution approach

Time complexity: O(n). Space complexity: 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.

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.

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

Key Insights

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

Common Mistakes

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

Interview Tips

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.

#226

Invert Binary Tree

Easy

Tree↗Depth-First Search↗Breadth-First Search↗Binary Tree↗Depth-First Search↗Recursion↗

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.