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.

Binary search tree search from root to leaf node

Dec. 10, 2017

Introduction

It is the great learning experience for me to do mock interview tonight at 10:00 PM. I met an architecture tonight, the peer showed me how to write correct code first, and then reminded me to write optimal code as well. The search in binary search tree can turn left and then turn right and then turn left, but invariant is that the path is from root to leaf node, and the answer is always found until the leaf node is reached.

Code study

I practiced this algorithm so many times, last time I wrote a blog about the experience one month ago. Here is the blog.

Today I solved the problem with the help of the peer.

There are two bounds to work on. One is the lower bound value which is smaller than given value, and then the other one is upper bound which is smaller than given value. In order to find the upper bound, we are looking for the first value which is bigger than given value first, and then find a smaller value until one is found. Then we are sure that we are find the upper bound value.

In my previous practices, the upper bound value should be searched in two directions, go right to find bigger value, and then go left to find smaller value.

Feedback is encouraging

Follow up 

Dec. 13 ,2017

Finally I have time to come out a test case to illustrate the search, and the steps are left and right and left and right and left.

Here is the binary search tree, given value 7, the largest smaller BST key should be 6. How to find the node with value 6?

Start from root node with value 10, and then visit every node in the above tree, and visit the leaf node with value 6, and the answer is 6.