CODEWITHSUNDEEP
algorithmperformancedata-structurestime-complexitybinary-search-tree
Mani Kant Tiwari
Mani Kant Tiwari

Reputation: 441

Tree : Performance comparison between stack implementation and recursive call of Traversal in BST

well I am currently learning data structure and algorithm. I got two methods of traversal in binary search tree. (1)-stack implementation
(2)-recursive call method

which one performance wise is better?

Upvotes: 0

Views: 92

Answers (1)

MD Ruhul Amin
MD Ruhul Amin

Reputation: 4502

As long as the algorithm remain same, performance should also be same. In your case: performance remains same because in both cases, stacks are used.

In, stack implementation programmer explicitly maintaining a stack for traversal. And in recursive call method, programs internal call stack is used for traversal.

EDIT:

and what about running time complexity ??

Running time complexity would be same for both of the cases. But execution time could be different depending on the implementation. As there is no code/implementation provided, "in general sense, recursion could take much longer time because

recursion (implemented naively) involves pushing a stack frame, jumping, returning, and popping back from the stack.

For more information you can check the following links:

  1. Is recursion faster than loops
  2. Looping versus recursion for improved application performance

Upvotes: 1

Related Questions