IT623 Algorithms & Data

Structures
Tree Searching
Tree searches
• A tree search starts at the root
and explores nodes from
A
there, looking for a goal node
(a node that satisfies certain
B C conditions, depending on the
problem)

D E F G • For some problems, any goal

node is acceptable (N or J), for
other problems, you want a
H I J K
minimum-depth goal node,
that is, a goal node nearest
L M N O P Q the root (only J)

Goal nodes
2
Depth-first searching
• A depth-first search (DFS)
A explores a path all the way to a
leaf before backtracking and
exploring another path
B C • For example, after searching A,
then B, then D, the search
D E F G backtracks and tries another path
from B
• Node are explored in the order
H I J K ABDEHLMNIOPCFGJKQ
• N will be found before J
L M N O P Q

3
How to do depth-first searching
• Put the root node on a stack,
while (stack is not empty) {
remove a node from the stack,
if (node is a goal node) return success,
put all children of node onto the stack,
}
return failure,

• At each step, the stack contains some nodes from each of a number of levels
• The size of stack that is required depends on the branching factor b
• While searching level n, the stack contains approximately b*n nodes

4
Recursive depth-first search

• Recursion is always implemented with a stack.

• Anything you can do with recursion, you can do with stacks, and vice-
versa

• search(node): print node and

if node is a goal, return success,
for each child c of node { print c and
if search(c) is successful, return success,
}
return failure,
5
Recursive depth-first search
• search(node): print node and
if node is a goal, return success,
for each child c of node { print c and
if search(c) is successful, return success,
}
return failure,

• The (implicit) stack contains only the nodes on a path from the root to
a goal
• When a solution is found, the path is on the (implicit) stack, and can be
extracted as the recursion “unwinds”
• You can do this by (for example) substituting pushing values onto a stack for
the above print statements

6
Breadth-first searching
• A breadth-first search (BFS)
A explores nodes nearest the root
before exploring nodes further
away
B C • For example, after searching A,
then B, then C, the search
D E F G proceeds with D, E, F, G
• Nodes are explored in the order
ABCDEFGHIJKLMNOPQ
H I J K
• J will be found before N

L M N O P Q

7
How to do breadth-first searching
• Put the root node on a queue,
while (queue is not empty) {
remove a node from the queue,
if (node is a goal node) return success,
put all children of node onto the queue,
}
return failure,

8
Comparison of algorithms
• Depth-first searching:
• Put the root node on a stack,
while (stack is not empty) {
remove a node from the stack,
if (node is a goal node) return success,
put all children of node onto the stack,
}
return failure,
• Breadth-first searching:
• Put the root node on a queue,
while (queue is not empty) {
remove a node from the queue,
if (node is a goal node) return success,
put all children of node onto the queue,
}
return failure,

9
How to do breadth-first searching
• Put the root node on a queue,
while (queue is not empty) {
remove a node from the queue,
if (node is a goal node) return success,
put all children of node onto the queue,
}
return failure,
• Just before starting to explore level n, the queue holds all the nodes at level n-1
• In a typical tree, the number of nodes at each level increases exponentially with the
depth
• Memory requirements may be infeasible
• When this method succeeds, it doesn’t give the path
• There is no “recursive” breadth-first search equivalent to recursive depth-first search

10
Depth- vs. breadth-first searching
• When a breadth-first search succeeds, it finds a minimum-depth
(nearest the root) goal node
• When a depth-first search succeeds, the found goal node is not
necessarily minimum depth
• For a large tree, breadth-first search memory requirements may be
excessive
• For a large tree, a depth-first search may take an excessively long time
to find even a very nearby goal node

11