LC: 272. Closest Binary Search Tree Value II - spiralgo/algorithms GitHub Wiki

272. Closest Binary Search Tree Value II:

The Essence: We can traverse the tree in an in-order traversal manner.

As it is a Binary Search Tree, in-order traversal would result in ascending order.

While we are traversing the tree starting from the smallest value, we will add the values into a LinkedList. But if we encounter a closer value, we will update the value at the first node (head) of LinkedList. We will repeat this until we reach the limit k.

Details:

Why this will work?

I think an explanation by Erdem will make it clear:

We compare the current value with the first element in the LinkedList, because the first element is most probably the furthest from our target value. If it's not so, that means the rest of the elements are further away from this pivot when we do inorder traversal (as the result of in-order is in ascending order)

You can find the detailed explanation here: https://github.com/spiralgo/algorithms/pull/299