With the help of a numerical example explain the Depth First Traversal of a tree

• Tweet
• Email

• Tweet
• Email

Depth traversal of a tree systematically visits all of its child nodes before visiting  any siblings. In case of binary trees, we perform pre-order, in-order or post-order traversal as depth first traversal techniques. Talking about general trees, follow the procedure below to traverse the nodes in depth first fashion.

 

Consider the given tree as above image. The depth-first traversal of this tree would be as follows:

5, 8, 2, 19, 4, 10, 13, 7, 16, 11, 22

Algorithm of DFS

dfs(T: tree, r: root node)

1. visit_dfs(r)

visit_dfs(u)

1. print u

2. for each child v of u

3.      if(!visited[v])

4.         visit_dfs(v)

5. visited[u] = TRUE

Explanation

When starting the tree and root node 5 is passed to the algorithm. It prints that 5. Because 5 has three children, it visits the first children 8 and prints it. And because 8 has its three children the first child 2 is visited and printed. Because 2 does not have any children, so it is marked ‘visited’. The recursive algorithm backtracks to 8 which still has two other children un-visited. The next unvisited child is 19. Thus it is printed and as well it child 4. Now, because 4 does not have any children, the program back tracks to 19 which does not have any unvisited child, it again backtracks to 8. 8 still has one more child not yet visited. Thus it visits that 10. Because 10 does not have any child, the program returns to 8. All the children of 8 are already visited thus it returns back to 5. This node 5 still has two more children unvisited. Thus it visits 13. Following the same method, it prints 7, 16, 11, 22.

This method of visiting all the children nodes of a tree before visiting the sibling nodes is known as depth first search.

---

This was the third question Kigozi Ronald from Makerere University, Uganda requested through email. He had originally asked to include a program too but I guess it would be too heavy for a question and a code snipet is not executable without importing all the tree class to code depth-first-search function. Anybody interested to share the program code are highly appreciated.

Any improvement or better answer for this question is heartily welcomed. Please leave your comment or write a mail to [email protected]

Tagged As: Algorithms and Data Structures, BFS, computer officer exam, Depth-First Search, Lok Sewa Aayog, Public Service Commission, Tree, Tree Data Structure