Tuesday, July 26, 2016

get 2nd largest item in bst

(n):
    if n == null:
        throw
    max2 = null
    if n.right != null:
        max2 = n
        while n.right != null:
            max2 = n
            n = n.right
    else if n.left != null:
        max2 = n.left
        while max2.right != null:
            max2 = max2.right
    return max2
Using a minheap of capacity k will work for any k (k = 2+).
// example 1
       4
   3       6 max2
 2   4    5  7
1 3

// example 2
       4
   3
 2   4 max2
1 3
// space: O(k), time: O(nlogk)
(n, k, minheap):
    if n == null:
        return
    if minheap.count() == k: // minheap.capacity() is k
        if n.value > minheap.peek().value:
            minheap.displace(n)
    if minheap.count() < k:
        minheap.insert(n)
    (n.left, k, minheap)
    (n.right, k, minheap)
[Hat tip to IC]

No comments:

Post a Comment