Daily Archives: January 19, 2016

Closest Binary Search Tree Value II

This one is from leetcode. Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

This is a very interesting problem. The best solution is that we maintain a k size window. We traverse tree in-orderly.  Let diffHead = abs(head – target), diffTail = abs(tail – target) and diff = max(diffHead, diffTail). So when k closest elements are in queue, we should have the minimum diff.

Suppose a below binary tree. When target  = 7, k = 3, the process is like:

closestinbt1

closestinbt2

closestinbt3

In this way, we know when nodes are [5, 7, 8], it gets the minimum diff.

check my code on github: link

h-index

https://leetcode.com/problems/h-index/

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Solution. This problem is a pretty easy one. 1st we sort the citation array in ascending order. Then we iterate from left to right in citation array, find the first position where its value is greater than the length between the position and array length.

Let’s think about below function. For point pi, its height is hi, the length from pi to right boundary is li. Basically, we need to find the first pi where hi is greater than li.
h_index

check my code on github: link