DFS Traversal

Question

If DFS algorithm applied starting from vertex ‘A’ which uses stack data structure then the height of stack is needed in worst case for DFS traversal is _________.

Comments

is it 7 ?

---

I think the answer should be 7.

---

I agree, it should be 7 because stack is not a tree. If it was a tree we would consider the number of edges, i.e., starting from 0. Since it is stack, which can be implemented either using LL or array, its height means the number of elements it can hold. Do not confuse it with recursion tree.

Answer 1

In worst case of DFS

Starting from "A"

Push A

Push  D

Push E

Push  G

Push F

Push  I

Push B  and now backtrack 

therefore 7 is height of stack Please note multiple sequences of worst case also possible one of them is traversing ADEGFIB

Comments

Don't you have to pop A to push the neighbors of A into the stack. https://www.programiz.com/dsa/graph-dfs. Also I found different implementations and explanations of DFS. Can you please clarify it. That would be a very big help. Thanks.

---

Thanks, I got clarification in a MIT courseware video

---

@sumit chakraborty i have same doubt, can you share the mit video.

Answer 2

maximum height of stack =6

Comments

Yes Definitely sir it should be 6 but in made easy test they took it 7 as they started counting from 1 not 0.

I too gave 6 as the answer

---

I am also referring made easy not book . Its Cleare mention  height of stack is equal to height of tree.

@Dont coll me sir @

---

If you have to store 7 nodes in the stack the height has to be 7. It's like keeping plates one over another.

Don't confuse with array indexing. Stack is a data structure which can be implemented by an array, linked lists, etc. Stack height is 0 with 1 element because array indexing starts from 0.

---

The height should be 7 only.I t’s like when we say the length of array is 5 means the array has the capacity to store 5 elements, then it will be 5 irrespective of the starting index chosen. If I choose start index as 0 then A[0,1,2,3,4] will be the indexes used whereas if I choose 1 as start index then, indexes will be A[1,2,3,4,5] but in both cases the capacity to store elements remains the same i.e. 5.