Design analysis and algorithm

MODULE 5

Basic Search and Traversal Techniques

Definition 1

: Traversal of a binary tree involves examining every node in the tree.

Definition 2

Search involves visiting nodes in a graph in a systematic manner, and may or may

not result into a visit to all nodes.

•Different nodes of a graph may be visited, possibly more than once, during traversal or

search

•If search results into a visit to all the vertices, it is called traversal

Binary tree traversal: Preorder, Inorder, and Postorder

in order to illustrate few of the binary tree traversals, let us consider the below binary tree:




Preorder traversal

: To traverse a binary tree in Preorder, following operations are carried out

(i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.

Therefore, the Preorder traversal of the above tree will outputs:

7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10




1

, 1. Algorithm
2. Algorithm preorder(t)
3. //t is a binary tree. Each node of t has
4. //three fields: lchild, data, and rchild.
5. {if t!=0 then
6. {Vist(t);
7. preorder(t->lchild);
8. preorder(t->rchild);
9. }}


Inorder traversal

: To traverse a binary tree in Inorder, following operations are carriedout

(i) Traverse the left most subtree starting at the left external node,

(ii) Visit the root, and

(iii) Traverse the right subtree starting at the left external node.

Therefore, the Inorder traversal of the above tree will outputs:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

1. Algorithm:
2. Algorithm inorder(t)
3. //t is a binary tree. Each node of tHas
4. //three fields: lchild, data, and rchild.
5. {
6. if t!=0 then
7. {postorder(t->lchild);
8. Visit(t);
9. postorder(t->rchild);
10. }}




Postorder traversal

: To traverse a binary tree in Postorder, following operations arecarriedout

(i) Traverse all the left external nodes starting with the left most subtree which is then
followed

by bubbleup all the internal nodes,

(ii) Traverse the right subtree starting at the left external node which is then followed by
bubble

2

, up allthe internal nodes, and

(iii) Visit the root.

Therefore, the Postorder traversal of the above tree will outputs:

0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

1. Algorithm:
2. Algorithm postorder(t)
3. //t is a binary tree. Each node of t has
4. //three fields: lchild, data,
5. and rchild.
6. {if t!=0 then
7. {postorder(t->lchild);
8. postorder(t->rchild);
9. Visit(t);
10. }
11. }


Graph Traversal

Graph traversal means visiting every vertex and edge exactly once in a well-defined order.
While using certain graph algorithms, you must ensure that each vertex of the graph is visited
exactly once. The order in which the vertices are visited are important and may depend upon
the algorithm or question that you are solving.

During a traversal, it is important that you track which vertices have been visited. The most
common way of tracking vertices is to mark them.

1.DepthFirst Traversal

• Depth first search (DFS) is an algorithm for traversing or searching a tree, tree
structure, or graph.
• One starts at the root (selecting some node as the root in the graph case) and explores
as far as possible along each branch before backtracking.
• Formally, DFS is an uninformed search that progresses by expanding the first child
node of the search tree that appears and thus going deeper and deeper until a goal
node is found, or until it hits a node that has no children.
• Then the search backtracks, returning to the most recent node it hasn't finished
exploring. In a non-recursive implementation, all freshly expanded nodes are
added to a stack for exploration.
•




3