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

import java.io.*; 
import java.util.*; 

public class Main{
    boolean b=false;
    public boolean stackSearch(Stack S,int x){
        if(!(S.isEmpty())){
            int val=(int)S.pop();
            if(x==val)
                b=true;
            else
                stackSearch(S,x);
       }
       return b; 
    }
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.print("Enter the stack size:");
        int size=sc.nextInt();
        System.out.println("Enter the elements into the stack:");
        Stack<Integer> S=new Stack<Integer>();
        for (int i=0;i<size;i++) {
            int str=sc.nextInt();
           S.push(str);
       }
       System.out.print("Enter the element to be serched:");
       int x=sc.nextInt();
       Main obj=new Main();
       System.out.println("Element Found:"+obj.stackSearch(S,x));
    }
} 

Time Complexity of the above recursive algorithm is:O(n)

Thank you! if you have any queries post it below in the comment section I will try my best to resolve your queries and I will add it to my answer if required. Please give upvote if you like it.