Get startedGet started for free

Depth First Search (DFS)

1. Depth First Search (DFS)

Let's study depth first search.

2. Tree/graph traversal

Traversal is the process of visiting all nodes of a tree or a graph. This can be performed with depth first search and breadth first search. We apply both to binary trees and graphs.

3. Depth first search - binary trees

There are three ways of traversing a binary tree using depth first search: in-order, pre-order, and post-order traversal.

4. In-order traversal

In-order traversal traverses the left subtree of the current node,

5. In-order traversal

followed by the current node, and finally,

6. In-order traversal

the right subtree. Starting from the root,

7. In-order traversal

we move to the root's left child

8. In-order traversal

and keep going down until we find a node with no left child.

9. In-order traversal

Since this node doesn't have a right child,

10. In-order traversal

we move backward.

11. In-order traversal

As this node has a right child,

12. In-order traversal

we move here.

13. In-order traversal

This node doesn't have any children,

14. In-order traversal

so we

15. In-order traversal

go backward.

16. In-order traversal

We repeat

17. In-order traversal

these

18. In-order traversal

steps

19. In-order traversal

for the

20. In-order traversal

rest of the

21. In-order traversal

tree's

22. In-order traversal

nodes.

23. In-order traversal

If applied to a binary search tree, output is in ascending order.

24. In-order traversal - implementation

Here is the recursive implementation. We start by checking if our node exists. If it does, we apply in_order traversal to the current_node's left child. We then visit the node by printing its value, and apply in_order traversal to current_node's right child. Output is shown. Complexity is O of n, where n is the number of nodes.

25. Pre-order traversal

Pre-order traversal first visits the current node,

26. Pre-order traversal

then traverses the left subtree,

27. Pre-order traversal

and finally, the right subtree. We visit

28. Pre-order traversal

the root

29. Pre-order traversal

and move to its left child.

30. Pre-order traversal

We visit it.

31. Pre-order traversal

We move to its left child

32. Pre-order traversal

and visit it.

33. Pre-order traversal

Then we go backward

34. Pre-order traversal

and move to

35. Pre-order traversal

the right child.

36. Pre-order traversal

We repeat

37. Pre-order traversal

the

38. Pre-order traversal

same

39. Pre-order traversal

steps

40. Pre-order traversal

for the

41. Pre-order traversal

rest

42. Pre-order traversal

of the

43. Pre-order traversal

tree's

44. Pre-order traversal

nodes.

45. Pre-order traversal - implementation

The recursive implementation is shown.

46. Post-order

Similarly, post-order traversal first traverses the current node's left subtree,

47. Post-order

then the right subtree,

48. Post-order

and finally, visits the current node.

49. When to use in-order, pre-order, and post-order

In-order traversal is commonly used in binary search trees to obtain the nodes' values in ascending order. Pre-order is used to create copies of a binary tree and get prefix expressions, as we'll see. Post-order is used to delete binary trees and get postfix expressions.

50. Depth first search - graphs

Let's study depth first search in graphs. As graphs can have cycles, we need to keep track of which vertices have been visited. The algorithm starts at any vertex. Then, it tracks the current vertex in a list. For each current node's adjacent vertex, if it has been visited, we ignore, but if it hasn't, we recursively perform depth first search.

51. Depth first search - graphs

Let's see how it works. We start with this vertex.

52. Depth first search - graphs

We visit it,

53. Depth first search - graphs

and move to its first adjacent vertex to apply depth first search. The computer needs to know that we didn't finish with vertex zero, so we push this information into the stack.

54. Depth first search - graphs

We visit vertex number one,

55. Depth first search - graphs

and apply depth first search to all adjacent vertices. Vertex zero has already been visited, so we ignore it,

56. Depth first search - graphs

and move to vertex two.

57. Depth first search - graphs

We visit it,

58. Depth first search - graphs

and apply the algorithm to its adjacent vertices. Zero

59. Depth first search - graphs

and one have already been visited, so we ignore them.

60. Depth first search - graphs

Vertex four is the last adjacent vertex for vertex two.

61. Depth first search - graphs

We visit it,

62. Depth first search - graphs

and keep

63. Depth first search - graphs

doing

64. Depth first search - graphs

the

65. Depth first search - graphs

same.

66. Depth first search - graphs

We finished visiting all the adjacent vertices for vertex three,

67. Depth first search - graphs

so we can pop it from the stack.

68. Depth first search - graphs

We do

69. Depth first search - graphs

the same

70. Depth first search - graphs

with

71. Depth first search - graphs

the rest

72. Depth first search - graphs

of the

73. Depth first search - graphs

vertices.

74. Depth first search - implementation

This is the recursive implementation. The complexity of this algorithm is O of V plus E, where V represents the number of vertices, and E the number of edges.

75. Let's practice!

Let's practice!

Create Your Free Account

or

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.