Question

Given a stack S and an element x, write a recursive algorithm that returns True if x is in S, or False otherwise. Note that your algorithm should not change the content in S. What is the time complexity of your algorithm?

Answer 1

Given a stack S and an element x, write a recursive algorithm that returns True if x is in S, or False otherwise.

Answer:

Stack is an Abstract Datatype, Hence We are assuming that a basic implementation of stack has below functionalities.

• push() − Pushing (inserting) an element on top of the stack.

• pop() − Removing (deleting) an element from the top of the stack.

• isEmpty() − check if stack is empty. and return True or False

Now the basic recursive algorithm to search an item X in a stack S.

Algorithm:

begin function Search_in_stack(stack S, item X):

   if S.is_empty() equals True:   #checks if stack is empty.
      return False 
   endif

   top_element ← S.pop()          #pop and store top element in a variable

   if top_element equals X:       #checks if the item is found
      S.push(top_element)         #to undo the pop operation, we push item again
      return True
   else:
      result ← Search_in_Stack(S,X) #if item not found, we recursively call algo.
      S.push(top_element)           #no matter what, we need to push item again
      return result                 #return the result of recursive step
   endif 
   
end function

Explanation :

1. This algortihm will pop the top element of stack until the stack becomes empty or required element is found.

2. To not change the content of stack , we need to push again the item, that we've poped.

Time Complexity : Big O (n)

Stack will be poped until it is empty, or until the item is found. Hence worst case time complexity for algorithm will be O(n). Because it will pop out all the elements.

Algorithm should not change the content in Stack, so before each return statement, the item will be pushed again. So stack will be unchanged finally.

Example :

S= [3,5,-1,2], X=-1

function calls -

search_in_stack( [3,5,-1,2], -1) => search_in_stack( [5,-1,2], -1) =>  search_in_stack( [-1,2], -1) => return True(element found)

stack will be restored, because push statements will push the corresponding items before returning the results in each recursive call.