Being interviewee: Find largest smaller binary search tree key

May 7 2018

Introduction

It is my algorithm called largest smaller binary search tree key. I had a mock interview at 8:00 PM with a young graduate student in California who had ACM ICPC contest experience. We had chat first after his mock interview algorithm, I did good job to pursuade him to write down a few lines of analysis before he wrote the code for the algorithm, specially keywords, ask, constraints. It is better to gather requirement from the problem statement, instead of memorizing all requirement in the head. It was pretty relax for me to work on the algorithm after the peer worked on his algorithm called Find difference pairs.

I chose to write the iterative solution without considering the recursive solution first, and then I told the peer that I had mocked interview this algorithm over 20 times. I was told that if the interviewer can tell that I memorize the algorithm, it will be no hire by a senior engineer before. So I told the peer that I still memorized the solution, I need to go left or right and I need to get into a loop as well. Only problem I had this time is how to construct a loop, what to loop on?

The peer was very experienced and he smiled, and then he asked me the question. Can you write a recursive solution for your algorithm? I said sure, but I have never written one using recursive solution within a 5 minutes period. So I did write down the recursive solution in less than 5 minutes. And then I argued myself to run test cases using given number 17, root number 20 as a test case. And then the peer ran a few test cases using 14, 17, 27, 25, and then he said that the code should work.

Recursive solution

It is my first time to write a five minute solution using recursive solution for the algorithm called largest smaller binary search tree key. It is definitely a good algorithm for the interview as the first interview algorithm. Compared to the iterative solution, I wrote more than five minutes since I had to argue to myself a few things, while loop construction, and then started from brute force solution to traverse the whole tree.

Here is my C# code.