BASIC TRAVERSAL AND
SEARCH TECHNIQUES
Outlines
Introduction
Binary Tree Traversal Methods
Preorder
Inorder
Postorder
Graph Search & Traversal Methods
Breadth First
Depth First
Introduction
In a traversal of a binary tree, each element of the
binary tree is visited exactly once.
In case of search of a graph (include tree and binary
tree), we may not examine all the vertices
During the visit of an element, all action (make a
clone, display, evaluate the operator, etc.) with
respect to this element is taken.
Binary Tree Traversal Methods
Preorder
Inorder
Postorder
Preorder Traversal
Preorder Example (visit = print)
b c
a b c
Preorder Example (visit = print)
b c
f
d e
g h i j
abdghei cf j
Preorder Of Expression Tree
* +
e f
+ -
a b c d
/ * +ab- c d+e f
Gives prefix form of expression!
Inorder Traversal
Inorder Example (visit = print)
b c
b a c
Inorder Example (visit = print)
b c
f
d e
g h i j
gdhbei af j c
Inorder By Projection (Squishing)
b c
f
d e
g h i j
g d h b e i a f j c
Inorder Of Expression Tree
/
* +
e f
+ -
a b c d
a + b * c - d/ e + f
Gives infix form of expression (sans parentheses)!
Postorder Traversal
Postorder Example (visit = print)
b c
bca
Postorder Example (visit = print)
b c
f
d e
g h i j
ghdi ebj f ca
Postorder Of Expression Tree
/
* +
e f
+ -
a b c d
ab+c d- * ef + /
Gives postfix form of expression!
Binary Tree Construction
Can you construct the binary tree, given two
traversal sequences?
Depends on which two sequences are given.
Inorder And Preorder
Inorder = g d h b e i a f j c
Preorder = a b d g h e i c f j
Scan the preorder left to right using the inorder to
separate left and right subtrees.
a is the root of the tree; gdhbei are in the left
subtree; fjc are in the right subtree.
gdhbei fjc
Inorder And Preorder
a
gdhbei fjc
preorder = a b d g h e i c f j
b is the next root; gdh are in a
the left subtree; ei are in the
right subtree.
b fjc
gdh ei
Inorder And Preorder
a
b fjc
gdh ei
preorder = d g h e i c f j a
d is the next root; g is in the b fjc
left subtree; h is in the right
subtree. d ei
g h
Inorder And Preorder
a
preorder = e i c f j b fjc
e is the next root; i is in
the right subtree. d e
g h i
a
preorder = c f j
b
c is the next root; fj is in the c
left subtree. d e
fj
g h i
Inorder And Preorder
preorder = f j
f is the next root; j is in the
right subtree.
a
b
c
d e
f
g h i j
Inorder And Postorder
Scan postorder from right to left using inorder to
separate left and right subtrees.
inorder = g d h b e i a f j c
postorder = g h d i e b j f c a
Tree root is a; gdhbei are in left subtree; fjc are in
right subtree.
Graph Search Methods
A vertex u is reachable from vertex v iff
there is a path from v to u.
2
3
8
1
4
5
9
10
6
7 11
Graph Search Methods
Many graph problems solved using a search
method.
Path from one vertex to another.
Is the graph connected?
Find a spanning tree.
Etc.
Commonly used search methods:
Breadth-first search.
Depth-first search.
Breadth-First Search
Visit start vertex and
put into a FIFO queue.
Repeatedly remove a
vertex from the queue,
visit its unvisited
adjacent vertices, put
newly visited vertices
into the queue.
Breadth-First Search Example
2
3
8
1
4
5
9
10
6
7 11
Start search at vertex 1.
Breadth-First Search Example
2 FIFO Queue
3 1
8
1
4
5
9
10
6
7 11
Visit/mark/label start vertex and put in a FIFO queue.
Breadth-First Search Example
2 FIFO Queue
3 1
8
1
4
5
9
10
6
7 11
Remove 1 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
2 4
8
1
4
5
9
10
6
7 11
Remove 1 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
2 4
8
1
4
5
9
10
6
7 11
Remove 2 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
4 5 3 6
8
1
4
5
9
10
6
7 11
Remove 2 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
4 5 3 6
8
1
4
5
9
10
6
7 11
Remove 4 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
5 3 6
8
1
4
5
9
10
6
7 11
Remove 4 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
5 3 6
8
1
4
5
9
10
6
7 11
Remove 5 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
3 6 9 7
8
1
4
5
9
10
6
7 11
Remove 5 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
3 6 9 7
8
1
4
5
9
1
0
6
7 11
Remove 3 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
6 9 7
8
1
4
5
9
10
6
7 11
Remove 3 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
6 9 7
8
1
4
5
9
1
0
6
7 11
Remove 6 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
9 7
8
1
4
5
9
10
6
7 11
Remove 6 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
9 7
8
1
4
5
9
10
6
7 11
Remove 9 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
7 8
8
1
4
5
9
10
6
7 11
Remove 9 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
7 8
8
1
4
5
9
10
6
7 11
Remove 7 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
8
8
1
4
5
9
10
6
7 11
Remove 7 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
8
8
1
4
5
9
10
6
7 11
Remove 8 from Q; visit adjacent unvisited vertices;
put in Q.
Breadth-First Search Example
2 FIFO Queue
3
8
1
4
5
9
10
6
7 11
Queue is empty. Search terminates.
All vertices reachable from the start vertex (including the
Path From Vertex v To Vertex u
Start a breadth-first search at vertex v.
Terminatewhen vertex u is visited or when
Q becomes empty (whichever occurs first).
Time
O(n2) when adjacency matrix used
O(n+e) when adjacency lists used (e is
number of edges)
Is The Graph Connected?
Start a breadth-first search at any vertex of the graph.
Graph is connected iff all n vertices get visited.
Time
O(n2) when adjacency matrix used
O(n+e) when adjacency lists used (e is number of edges)
Connected Components
Start a breadth-first search at any as yet unvisited vertex
of the graph.
Newly visited vertices (plus edges between them) define a
component.
Repeat until all vertices are visited.
Connected Components
2
3
8
1
4
5
9
1
0
6
7 11
Spanning Tree
Start a breadth-first search at any vertex of
the graph.
If graph is connected, the n-1 edges used to
get to unvisited vertices define a spanning tree
(breadth-first spanning tree).
Time
O(n2) when adjacency matrix used
O(n+e) when adjacency lists used (e is
number of edges)
Depth-First Search
Note that vertices adjacent
from v are examined one at
a time.
As soon as an unreached
adjacent vertex w is found,
a DFS(w) is done.
Remaining vertices
adjacent from v are
examined after DFS(w)
completes.
Depth-First Search Example
2
3
8
1
4
5
9
1
0
6
7 11
Start search at vertex 1.
Label vertex 1 and do a depth first search from either 2 or 4.
Suppose that vertex 2 is selected.
Depth-First Search Example
2
3
8
1
4
5
9
10
6
7 11
Label vertex 2 and do a depth first search from either 3, 5, or 6.
Suppose that vertex 5 is selected.
Depth-First Search Example
2
3
8
1
4
5
9
1
0
6
7 11
Label vertex 5 and do a depth first search from either 3, 7, or 9.
Suppose that vertex 9 is selected.
Depth-First Search Example
2
3
8
1
4
5
9
10
6
7 11
Label vertex 9 and do a depth first search from either 6 or 8.
Suppose that vertex 8 is selected.
Depth-First Search Example
2
3
8
1
4
5
9
1
0
6
7 11
Label vertex 8 and return to vertex 9.
From vertex 9 do a DFS(6).
Depth-First Search Example
2
3
8
1
4
5
9
10
6
7 11
Label vertex 6 and do a depth first search from either 4 or 7.
Suppose that vertex 4 is selected.
Depth-First Search Example
2
3
8
1
4
5
9
1
0
6
7 11
Label vertex 4 and return to 6.
From vertex 6 do a DFS(7).
Depth-First Search Example
2
3
8
1
4
5
9
10
6
7 11
Label vertex 7 and return to 6.
Return to 9.
Depth-First Search Example
2
3
8
1
4
5
9
1
0
6
7 11
Return to 5.
Depth-First Search Example
2
3
8
1
4
5
9
1
0
6
7 11
Do a DFS(3).
Depth-First Search Example
2
3
8
1
4
5
9
1
0
6
7 11
Label 3 and return to 5.
Return to 2.
Depth-First Search Example
2
3
8
1
4
5
9
10
6
7 11
Return to 1.
Depth-First Search Example
2
3
8
1
4
5
9
10
6
7 11
Return to invoking method.
Depth-First Search Properties
Same complexity as BFS.
Same properties with respect to path finding,
connected components, and spanning trees.
Edges used to reach unlabeled vertices define a
depth-first spanning tree when the graph is
connected.
There are problems for which BFS is better than DFS
and vice versa.
Thanks for your Attention
Q&A
