# Coding Questions - DFS and BFS¶

You have to master the most used techniques and be able to apply them on
1. Tree

• DFS

• Recursive
• Iterative
• BFS

• Recursive
• Iterative
2. Matrix

• DFS

• Recursive:

```class Solution(object):
def numIslands(self, grid):
def helper(grid, visited, row, col, res):
if len(grid) > row >= 0 and len(grid) > col >= 0:
if not visited[row][col]:
visited[row][col] = True
if grid[row][col] == '1':
res.append((row, col))
helper(grid, visited, row + 1, col, res)
helper(grid, visited, row - 1, col, res)
helper(grid, visited, row, col + 1, res)
helper(grid, visited, row, col - 1, res)

res = []
visited = [[False for _ in range(len(grid))] for __ in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid)):
tmp = []
helper(grid, visited, i, j, tmp)
if tmp:
res.append(tmp)
return len(res)
```
• Iterative:

```def numIslands_stack(self, grid):
res = []
visited = [[False for _ in range(len(grid))] for __ in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid)):
tmp = []
stack = [(i, j)]
while stack:
row, col = stack.pop()
if len(grid) > row >= 0 and len(grid) > col >= 0:
if not visited[row][col]:
visited[row][col] = True
if grid[row][col] == '1':
tmp.append((row, col))
stack.append((row+1, col))
stack.append((row-1, col))
stack.append((row, col+1))
stack.append((row, col-1))
if tmp:
res.append(tmp)
return len(res)
```
• BFS

• Recursive

• Iterative:

```def numIslands_queue(self, grid):
res = []
visited = [[False for _ in range(len(grid))] for __ in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid)):
queue = [(i, j)]
tmp = []
while queue:
n = len(queue)
while n:
row, col = queue.pop(0)
n -= 1
if len(grid) > row >= 0 and len(grid) > col >= 0:
if not visited[row][col]:
visited[row][col] = True
if grid[row][col] == '1':
tmp.append((row, col))
queue.append((row + 1, col))
queue.append((row - 1, col))
queue.append((row, col + 1))
queue.append((row, col - 1))
if tmp:
res.append(tmp)
return len(res)
```
3. Graph

Have a process idea which is to have 3 colors to indicate the state and mark all vertices from WHITE to GRAY and then to BLACK to indicate the search is completed.

Always keep in mind that Graph is consisted by Vertex and Edge.

Running time is O(V+E).

• DFS
• Property
• During search, we can set 2 timestemp v.d and v.f to indicate first discover and blacken the vertex.

• Parenthesis structure.

• First explore an edge (u, v):
• WHITE indicates a tree edge
• GRAY indicates a back edge
• BLACK indicates a forward or cross edge
• Recursive

• Iterative

• BFS
• Property
• During search, we can set the distance between source and this vertex
• Recursive

• Iterative

## Level Order Traversal of Binary Tree¶

DFS:

```def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
def recursive(res, root, level):
if not root:
return
if level < len(res):
res[level].append(root.val)
else:
res.append([root.val])
recursive(res, root.left, level+1)
recursive(res, root.right, level+1)
res = []
recursive(res, root, 0)
return res[::-1]

1.    TreeNode visit = root;
Stack<TreeNode> stack = new Stack();
2.    while (visit != null || !stack.empty()) {
3.        while (visit != null) {
stack.push(visit);
visit = visit.left;
}
TreeNode next = stack.pop();
visit = next.right;
doSomethingWith(next.val);
}
```

BFS:

```def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
final = []
queue = []
queue.append(root)
while queue:
res = []
# we have queue and we need to get each level
# this is done by get the size of queue which is the size of the level
n = len(queue)
while(n):
node = queue.pop(0)
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
n -= 1
final.append(res)
return final[::-1]
```

A*:

## Tip¶

1. when you want to update the matrix, remember to update all the vertices

better to use a paradigm for v in vertices:

do dfs or bfs

2. Do a BFS on multiple sources

push every node into queue

3. It’s different between Inorder Traversal and a simple DFS, and you can tell from the way stack method is implemented

```# InOrder Traverse Stack
def traverse_stack(root):
stack = []
res = []
while(True):
while(root):
stack.append(root)
root = root.left
if not stack:
return res
node = stack.pop()
res.append(node.val)
root = node.right
return res

# PreOrder
def traverse_stack(root):
res = []
stack = [root]
while stack:
node, path = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
```