(n): if n == null: return // max2 could be parent of max max2 = null max = n while max.right != null: max2 = max max = max.right // if max.left is not null then max2 is // max.left's rightmost if max.left != null: max2 = max.left while max2.right != null: max2 = max2.right return max2Using 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 3With duplicates and

`minheap(2, n => n.value)`

, traversing the left subtree will give wrong node, node 1 of level 2 (node 1 of level 1 with be displaced by node 2). Traversing right subtree first (as there are no dupes) will fix this but will not work for 3rd largest. To fix that minheap should look at value and if same then at level (same value nodes with greater level get pushed up), so `minheap(k, comparer)`

.// dupes example 1 1 2

// space: O(k), time: O(nlogk) (n, k, minheap = minheap(2, comparer)): 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.right, k, minheap) (n.left, k, minheap) comparer: // node with greater value is greater // for same value, node with lesser level is greater int compare(n, other): c = n.value.compare(other.value) if c == 0: c = n.level.compare(other.level) * -1 return c[Hat tip to IC]

## No comments:

## Post a Comment