Leetcode 272: Closest binary search tree value II

July 1, 2018

Introduction

It is a hard level algorithm and also relate to binary search tree. I like to work on it using 30 minutes. Now it is 2:12 PM. First 20 minutes to think about a solution, next 10 minutes to study the solution.

Now it is 2:26 PM. I fount that I had experience to work on mock interview algorithm called next largest successor. I already went through the blog and found one with very good discussion about the algorithm. Here is the blog link.

One idea to use two stacks

I just copied the note from the blog to here:

If we do inorder depth-first traverse (left->root->right) of a binary search tree, we can get an ascending sorted list of elements. If we do reverse inorder depth-first traverse (right->root->left) of a binary search tree, we can get a descending sorted list.

So we create two stacks to store. Stack 1 records the ascending sorted list but it terminates before the element which <= target. (line 40). Stack 2 records the descending sorted list but it terminates at the element which < target. (line 42). (You can also make the first inequality with less than, and the second inequality with larger than or equal to. The main point is that the two stacks shouldn’t contain any element at the same time.)

At last you peek at stack 1 and stack 2. You need to pop element into res list from whichever stack has the top element closer to target.