question
Given a stack, find an element in the middle position of the stack. Optimize for space.
Recursion would be most efficient.
Using recursion, calculate how large the stack is on the way down and then return the appropriate element on the way back up.


int getMiddle(stack* s, int pos, int* depth)
    if (s.empty()) // reached bottom of stack
       *depth = pos;
       return 0;

    int value = s.pop();
    int result = getMiddle(s, pos + 1, depth)
    s.push(value);

    if (pos == *depth/2)
       return value;

    return result;


int depth;
getMiddle(&s, 0, &depth)


Thoughts or alternate solution? Let us know in the comments below!