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.