binary search tree inorder successor

January 6, 2018

Introduction

It is very exciting time to meet a peer on mock interview. After the peer solved the problem perfectly, I asked to give him another algorithm to solve. Because I like to evaluate how good he is and also learn the algorithm through the discussion. Keep it a secret, I also like to develop the skills to evaluate the candidate technical strength on recursive solution.

So today after 10:00 AM mock interview, I asked the peer to solve the binary search tree inorder successor.

Usually what I did is to go to the above code review link, and get the binary search tree image url first, and then open a page on codeshare. I put together the problem statement with tree node data structure, the function definition with two arguments.

Peer discussion

Here is the transcript for our discussion. The peer chose to use the idea to write an inorder traversal of the tree using recursive function, and then piggyback the idea to check if the given node is found. Next visit should be the successor.

The discussion between the two peers are related where to put the successor checking. My argument is to put at the beginning of the function, and then peer likes to put else clause. I expressed the concern of a bug to write this way.

Later the peer told me that the search is O(n) time complexity where n is the size of the tree. The optimal solution can be better, O(logn).