DS&A

Exercises: Searching Trees

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)
   Check your answers to 1. and 2. against your functions’ output.
   
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?

• Tags: 
• exercises, BFS, DFS, trees, search, algorithms