2 votes 2 votes 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 _________. Algorithms depth-first-search algorithms graph-algorithms numerical-answers made-easy-test-series + – sumit chakraborty asked Jan 11, 2018 • retagged Jul 8, 2022 by Lakshman Bhaiya sumit chakraborty 1.3k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Ashwin Kulkarni commented Jan 11, 2018 reply Follow Share is it 7 ? 0 votes 0 votes Kushagra Chatterjee commented May 6, 2018 reply Follow Share I think the answer should be 7. 1 votes 1 votes Akhilesh Singla commented May 6, 2018 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes 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 Sandeep Suri answered Jan 11, 2018 • selected Jan 12, 2018 by sumit chakraborty Sandeep Suri comment Share Follow See all 3 Comments See all 3 3 Comments reply sumit chakraborty commented Jan 12, 2018 reply Follow Share 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. 0 votes 0 votes sumit chakraborty commented Jan 12, 2018 reply Follow Share Thanks, I got clarification in a MIT courseware video 0 votes 0 votes Sandy Sharma commented Jan 4, 2019 reply Follow Share @sumit chakraborty i have same doubt, can you share the mit video. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes maximum height of stack =6 abhishekmehta4u answered May 6, 2018 abhishekmehta4u comment Share Follow See all 4 Comments See all 4 4 Comments reply Na462 commented May 6, 2018 reply Follow Share 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 0 votes 0 votes abhishekmehta4u commented May 6, 2018 reply Follow Share I am also referring made easy not book . Its Cleare mention height of stack is equal to height of tree. @Dont coll me sir @ 0 votes 0 votes gauravkc commented May 6, 2018 reply Follow Share 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. 2 votes 2 votes Ankit Raina 7 commented Jan 19, 2021 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.