Question

Use java .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

Recursive algorithm to search an element in a Stack

searchStackElement(Stack S, element x) { // to find the element in stack
if stack is empty   // check for empty stack
return False // for empty stack return false
else
if stack is not empty // check for stack is empty or not
    temp = pop(s) // take top element in temp variable
if(temp == x) // compare with the input element
return True;    // return True if element present in stack
else
return false;    // retrun False if element is not present in stack
  S = S - 1 ; // reduce stack top by 1 to find element at next position
  searchStackElement(Stack S, element x); // recursive call to the stack for element
}

The time complexity of the algorithm is O(n) in worst case, element present at buttom in stack.
The time complexity of the algorithm is O(1) in Best case , element present at top of the stack.

============================END=============================
Comment if any query.