[LeetCode] LC226 - Invert Binary Tree

Description

Invert a binary tree.

Input:

1
2
3
4
5
6
7
8
9
10
11
12
     4
/ \
2 7
/ \ / \
1 3 6 9
Output:

4
/ \
7 2
/ \ / \
9 6 3 1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f* off.

> Solve problem here

Thoughts

I was not able to solve this problem at the begining. I felt myself so stupid after seeing the DFS approach for just 5 lines. After two weeks from previous submission. I was able to recall all three different approaches.

Recursive DFS (Top-down)

Recursive DFS is acutally very straight forward. For each node, swap its left & right child. Recursively call invertTree(left) to the rest of the tree.

1
2
3
4
5
6
7
8
9
10
11
12
// recursive dfs, top-down, might cause stack overflow
// time: O(n)
// space: O(logn) for recursive stack
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
TreeNode left = root.left;
root.left = root.right;
root.right = left;
invertTree(root.left);
invertTree(root.right);
return root;
}

Recursive DFS (Bottom-up)

The above approach recursive dfs use top-down approach, where swap is performed along the way from top to bottom. The bottom-up approach is also possible.

1
2
3
4
5
6
7
8
9
10
// recurive dfs, bottom-up, might cause stack overflow 
// time: O(n)
// space: O(logn) for recursive stack
public TreeNode invertTree_dfs(TreeNode root) {
if (root == null) return root;
TreeNode left = root.left, right = root.right;
root.left = invertTree_dfs(right);
root.right = invertTree_dfs(left);
return root;
}

The bottom-up approach first go down to the far left node in the left subtree. Then swap start from there and its right subtree and return node to upper level. The process is very similiar to pre-order traversal.

Iterative DFS

Both recursive dfs approach might cause stack overflow if tree is extremely unbalanced, hence the height of tree might be large to cause stack overflow. Let’s take a look at the iterative approach with Stack data structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// iterative dfs no stack overflow
// time: O(n)
// space: O(logn) for user stack
public TreeNode invertTree_dfs2(TreeNode root) {
if (root == null) return root;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);

while (!stack.isEmpty()) {
TreeNode node = stack.pop();

// swap
TreeNode left = node.left;
node.left = node.right;
node.right = left;

// add to queue, level order process
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}

return root;
}

As we can see, iteative dfs, indeed, is very similiar to recursive top-down approach. The recursive top-down approach uses an implicit Stack and iterative dfs uses an explicit Stack.

Iterative BFS

Benefit from the nature of this problem, we can also use BFS to solve it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// BFS, change stack to queue
// time: O(n)
// space: O(n) for user queue (last layer of complete binary tree n/2 nodes)
public TreeNode invertTree_bfs(TreeNode root) {
if (root == null) return root;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.offer(root);

while (!stack.isEmpty()) {
TreeNode node = stack.poll();

// swap
TreeNode left = node.left;
node.left = node.right;
node.right = left;

// add to queue, level order process
if (node.left != null) stack.offer(node.left);
if (node.right != null) stack.offer(node.right);
}

return root;
}

BFS approach uses level order traversal to push node and swap them in order. The overall strcture is very similiar to the iterative dfs version.

Summary:

  • DFS recurisve (top-down)
  • DFS recurisve (bottom-up, preorder traversal)
  • DFS iterative (stack)
  • BFS iterative (queue, level-order traversal)

Logs

  • 02/03/2019 Add solutions

Reference