Katkat
Back

Second-Smallest Value in a Min Tournament Tree in Logarithmic Time

LinkedInSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Given a full binary tournament tree stored in array order, where each internal node holds the smaller of its two children, return the second-smallest leaf value in logarithmic time. It tests reasoning about how a knockout structure constrains where the runner-up can be, array-based tree indexing, and justifying a partial search.

A tournament tree records a knockout competition among n players with distinct values. Every leaf holds one player's value, and every internal node has exactly two children and holds the smaller of its two children's values, so the root holds the minimum of all values. Find the second-smallest value in the tree.

Function Signature

second_minimum(tree: list[int]) -> int

Tree Layout

  • tree stores a full binary tree in array order and has length 2n - 1, where n is the number of leaves.
  • The children of index i are at indices 2i + 1 and 2i + 2. Indices 0 through n - 2 are internal nodes and always have both children; indices n - 1 through 2n - 2 are leaves.
  • For every internal index i, tree[i] == min(tree[2i + 1], tree[2i + 2]).

Output

Return the second-smallest of the n leaf values. Because leaf values are distinct, this value is unique.

Performance Requirement

The expected time complexity is O(log n), not counting the cost of receiving the input. A solution that examines every leaf does not meet the requirement.

Constraints

  • 2 <= n <= 100000, so 3 <= len(tree) <= 199999.
  • Leaf values are distinct integers in [-1000000000, 1000000000].
  • The input always satisfies the layout and the minimum property described above.

Examples

Input: tree = [1,3,1,5,3,8,1]

Output: 3

The leaves at indices 3 to 6 are 5, 3, 8, and 1. The minimum is 1, and the next smallest value is 3.

Input: tree = [2,2,4,9,2]

Output: 4

Here n = 3. Index 0 has children at indices 1 and 2, index 1 has children at indices 3 and 4, and the leaves at indices 2, 3, and 4 are 4, 9, and 2.

Input: tree = [-3,6,-3]

Output: 6