Solution to Closest Binary Search Tree Value II

5 May

This question is available on both Leetcode (No. 270) and Lintcode (No. 901). The question is not too hard, if we do not chase the best time complexity. For example, we can traversal all the nodes and book-keep the closest nodes.

The challenging is “Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?” Reasonably, the answer is yes. We can do it better than O(n), as O(logN + k). However, it took me quite a few days to find out the right solution.

When I got stuck with this problem, I tried to Google the other blogs. Unfortunately, among the pages I visited, some so-called O(logN + K) solutions are essentially O(N + k). For example, some solution prepare all the predecessors and successors in functions like getPredecessor(TreeNode root, double target, Stack precedessor), where the function fills the stack with all qualified nodes. Since nearly all nodes will be either predecessor or successor, these functions are O(N).

In fact, the key is how to get the predecessor and successor without visiting the whole tree. And the answer is a variable of iteration-based in-order traversal.

Leave a Reply

Your email address will not be published.

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!