FastPrepSecond Minimum in a Tournament Tree

Second Minimum in a Tournament Tree

LinkedIn logoLinkedIn● MediumNEW GRADPHONE SCREEN
Learn

Problem statement

You are given the root of a tournament tree. Every node has either zero or two children, and each internal node stores the smaller value of its two children.

All leaf values are distinct, and the tree has at least two leaves. Return the second-smallest leaf value.

Function

secondMin(root: TreeNode) → int

Examples

Example 1

root = [2,2,3,4,2,5,3]return = 3

The smallest leaf is 2, and 3 is the next smallest leaf.

Example 2

root = [1,1,2,1,7,null,null,1,4]return = 2

The minimum winner travels through a deep full-tree chain; the next leaf value is 2.

Example 3

root = [-5,-5,0,-5,-2,0,3]return = -2

Negative values obey the same tournament invariant, so -2 is second.

Constraints

  • The tree contains between 3 and 10001 nodes.
  • Every node has either zero or two children.
  • For every internal node, node.val = min(node.left.val, node.right.val).
  • All leaf values are distinct.
  • -1000000000 ≤ node.val ≤ 1000000000
  • The tree contains at least two leaves, so the answer always exists.

More LinkedIn problems

See LinkedIn hiring insights
public int secondMin(TreeNode root) {
    // write your code here
}
root[2,2,3,4,2,5,3]
expected3
Checking account…