# DS&A

Data Structures and Algorithms

## Exercises: Searching Trees

Apr 092018

Before 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

1. Write down the order in which the nodes would be visited by DFS.
2. Write down the order in which the nodes would be visited by BFS.
3. Modify the recursive DFS and BFS functions by adding the following `print` statement when a node is visited:
• `print('Visiting node', node.value)`
4. 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?

## New comment

Your comment will not appear until a moderator approves it.

Atom

hosted on werp.site