## Exercises: Searching Trees

Apr 092018Before attempting these exercises, you should read the posts on depth-first search (DFS) and breadth-first search (BFS).

The following Python code defines a tree using the list-of-children data structure:

```
class Node:
def __init__(self, value, children=None):
if children is None:
children = []
self.value = value
self.children = children
def __repr__(self):
if self.children:
fmt = 'Node({!r}, {!r})'
else:
fmt = 'Node({!r})'
return fmt.format(self.value, self.children)
root_node = Node(8, [
Node(4, [
Node(3),
Node(6)
]),
Node(9)
])
```

The tree is shown below as a node/link diagram:

### Exercises

- Write down the order in which the nodes would be visited by DFS.
- Write down the order in which the nodes would be visited by BFS.
- Modify the recursive DFS and BFS functions by adding the following
`print`

statement when a node is visited:`print('Visiting node', node.value)`

- Modify the iterative DFS function in the same way. Notice that the nodes are not visited in the same order as the recursive DFS function — why not? How would you change iterative DFS so that it does?

## There are no published comments.