Depth First Search (DFS) – Interview Questions & Practice Problems

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the root (selecting some arbitrary node as the root in the case of a graph) and explore as far as possible along each branch before backtracking.

The following graph shows the order in which the nodes are discovered in DFS:

 
In this post, we have listed out commonly asked interview questions that can be solved using DFS:

1. Depth First Search (DFS)
2. Arrival and departure time of vertices in DFS
3. Types of edges involved in DFS and relation between them
4. Determine whether a graph is Bipartite using DFS
5. Topological Sort Algorithm for DAG
6. Transitive closure of a graph
7. Determine whether an undirected graph is a tree (Acyclic Connected Graph)
8. 2–Edge Connectivity in a graph
9. 2–Vertex Connectivity in a graph
10. Check if a digraph is a DAG (Directed Acyclic Graph) or not
11. Check if a graph is strongly connected or not
12. Check if a graph is strongly connected or not using one DFS Traversal
13. Find the cost of the shortest path in DAG using one pass of Bellman–Ford
14. Find correct order of alphabets in a given dictionary of ancient origin
15. Find the longest path in a Directed Acyclic Graph (DAG)
16. Eulerian cycle in directed graphs
17. Find root vertex of a graph
18. Check whether an undirected graph is Eulerian
19. Check if a set of words can be rearranged to form a circle
20. Check if an undirected graph contains a cycle or not
21. Traverse a given directory using BFS and DFS in Java
22. Find the path between given vertices in a directed graph
23. Construct a directed graph from an undirected graph that satisfies given constraints
24. Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix
25. Replace all occurrences of 0 that are surrounded by 1 in a binary matrix
26. Find the path from source to destination in a matrix that satisfies given constraints
27. Find all occurrences of the given string in a character matrix
28. Find the length of the longest path in a matrix with consecutive characters
29. Flood Fill Algorithm
30. Generate a list of possible words from a character matrix
31. Lexicographic sorting of a given set of keys
32. Find the maximum occurring word in a given set of strings
33. Find first k maximum occurring words in a given set of strings
34. Find the shortest unique prefix for every word in an array
35. Inorder Tree Traversal
36. Preorder Tree Traversal
37. Postorder Tree Traversal
38. Print bottom view of a binary tree
39. Print top view of a binary tree
40. In-place convert a binary tree to its sum tree
41. Determine whether the given binary tree nodes are cousins of each other
42. Print cousins of a given node in a binary tree
43. Check if a binary tree is a sum tree or not
44. Determine whether a binary tree is a subtree of another binary tree
45. Find the diameter of a binary tree
46. Convert a binary tree to its mirror
47. Print all paths from the root to leaf nodes of a binary tree
48. Find ancestors of a given node in a binary tree
49. Find the diagonal sum of a binary tree
50. Sink nodes containing zero to the bottom of a binary tree
51. Convert a binary tree to a full tree by removing half nodes
52. Truncate a binary tree to remove nodes that lie on a path having a sum less than k
53. Find maximum sum root to leaf path in a binary tree
54. Check if a binary tree is height-balanced or not
55. Convert binary tree to Left-child right-sibling binary tree
56. Print all paths from leaf to root node of a binary tree
57. Iteratively print the leaf to root path for every leaf node in a binary tree
58. Find all nodes at a given distance from leaf nodes in a binary tree
59. Count all subtrees having the same value of nodes in a binary tree
60. Find the maximum difference between a node and its descendants in a binary tree
61. Construct a binary tree from inorder and preorder traversal
62. Construct a binary tree from inorder and postorder traversals
63. Construct a binary tree from inorder and level order sequence
64. Construct a full binary tree from the preorder sequence with leaf node information
65. Construct a full binary tree from a preorder and postorder sequence
66. Find postorder traversal of a binary tree from its inorder and preorder sequence
67. Set next pointer to the inorder successor of all nodes in a binary tree
68. Find preorder traversal of a binary tree from its inorder and postorder sequence
69. Clone a binary tree with random pointers
70. Threaded Binary Tree – Overview and Implementation
71. Determine if a binary tree satisfies the height-balanced property of a red–black tree
72. Construct an ancestor matrix from a binary tree
73. Find all possible binary trees having the same inorder traversal
74. Perform boundary traversal on a binary tree
75. Check if each node of a binary tree has exactly one child
76. Evaluate a Binary Expression Tree
77. Construction of an expression tree
78. Fix children-sum property in a binary tree
79. Create a mirror of an m–ary tree
80. Print a two-dimensional view of a binary tree
81. Determine whether a given binary tree is a BST or not
82. Fix a binary tree that is only one swap away from becoming a BST
83. Find the size of the largest BST in a binary tree
84. Construct a Cartesian tree from an inorder traversal
85. Calculate the height of a binary tree with leaf nodes forming a circular doubly linked list
86. Link nodes present in each level of a binary tree in the form of a linked list
87. Extract leaves of a binary tree into a doubly-linked list
88. Find the vertical sum of a binary tree
89. In-place convert a binary tree to a doubly-linked list
90. Check whether the leaf traversal of given binary trees is the same or not
91. Efficiently print all nodes between two given levels in a binary tree
92. Calculate the height of a binary tree
93. Delete a binary tree
94. Level order traversal of a binary tree
95. Spiral order traversal of a binary tree
96. Reverse level order traversal of a binary tree
97. Print left view of a binary tree
98. Find the next node at the same level as the given node in a binary tree
99. Print diagonal traversal of a binary tree
100. Invert Binary Tree
101. Convert a binary tree into a doubly-linked list in spiral order
102. Check if a binary tree is a min-heap or not
103. Invert alternate levels of a perfect binary tree
104. Perform vertical traversal of a binary tree
105. Compute the maximum number of nodes at any level in a binary tree
106. Print right view of a binary tree
107. Find the minimum depth of a binary tree
108. Depth-First Search (DFS) vs Breadth-First Search (BFS)
109. Print nodes of a binary tree in vertical order
110. Find k’th smallest and k’th largest element in a BST
111. Convert a binary tree to BST by maintaining its original structure
112. Remove nodes from a BST that have keys outside a valid range
113. Find a pair with the given sum in a BST
114. Find k’th smallest node in a Binary Search Tree (BST)
115. Update every key in a BST to contain the sum of all greater keys
116. Check if a given sequence represents the preorder traversal of a BST
117. Build a Binary Search Tree from a postorder sequence
118. Build a Binary Search Tree from a preorder sequence
119. Count subtrees in a BST whose nodes lie within a given range
120. Print complete Binary Search Tree (BST) in increasing order
121. Merge two BSTs into a doubly-linked list in sorted order
122. Construct a height-balanced BST from an unbalanced BST
123. Construct a height-balanced BST from a sorted doubly linked list
124. Find a triplet with the given sum in a BST
125. Convert a Binary Search Tree into a Min Heap