Quick Overview

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.

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

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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`

Overview: 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. Given the tree, return the second-smallest of the `n` leaf values. ### 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])`. - When `n` is not a power of two the leaves do not all sit at the same depth, but the index ranges above still describe exactly which positions are leaves. ### Output Return the second-smallest of the `n` leaf values, as an integer. Because leaf values are distinct, this value is unique, so there is exactly one correct answer for every input. ### 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. ### Examples Example 1 Input: `tree = [1, 3, 1, 5, 3, 8, 1]` Output: `3` Here `n = 4`, and the leaves at indices 3 to 6 are 5, 3, 8, and 1. The minimum is 1, and the next smallest leaf value is 3. Example 2 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. The minimum is 2, and the next smallest leaf value is 4.

Constraints

  • 2 <= n <= 100000, so 3 <= len(tree) <= 199999.
  • tree stores a full binary tree in array order with length 2n - 1; 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]).
  • Leaf values are distinct integers in [-1000000000, 1000000000].
  • The input always satisfies the layout and the minimum property described above.
  • No value can exceed 2^31 - 1 and no sum or product is required, so Java int and C++ int are sufficient.
  • 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.

Examples

Input: ([1, 3, 1, 5, 3, 8, 1],)

Expected Output: 3

Explanation: n = 4; the leaves at indices 3..6 are 5, 3, 8, 1. The minimum 1 sits at index 6, so the values it defeated are tree[1] = 3 (at the root) and tree[5] = 8; the smaller is 3.

Input: ([2, 2, 4, 9, 2],)

Expected Output: 4

Explanation: n = 3, so the leaves 4, 9, 2 sit at two different depths (index 2 is a leaf while index 1 is internal). The minimum 2 defeated 4 at the root and 9 one level down; the smaller is 4.

Hints

  1. The root already tells you the smallest value for free. The whole question is which of the remaining leaf values can possibly come next.
  2. Only a small number of leaf values are plausible answers. Try to characterize them from the tree structure instead of scanning all n leaves.
  3. The target complexity is about the height of the tree, which hints at how many nodes you are allowed to look at. Note that when n is not a power of two, leaves sit at different depths, so base your stopping rule on the leaf index range n - 1 .. 2n - 2.

Loading coding console...

Show the approach

Approach

The root holds the global minimum m. Because leaf values are distinct, m occupies exactly one leaf, and the nodes equal to m are exactly the nodes on the single path from the root down to that leaf.

Key claim: the second smallest leaf value s is one of the values that m directly defeated on that path. Suppose s lost its comparison to some value v. Then v < s and v is a leaf value, so v is either m or a leaf value strictly between m and s; the latter cannot exist because s is the second smallest. Hence v = m, meaning s is the sibling value at some node along m's path. Conversely, every such sibling value is a leaf-derived value greater than m, so the smallest of them is exactly s.

Algorithm: start at index 0 with best unset. While the current index i is internal (equivalently 2i + 1 < len(tree), equivalently i <= n - 2), look at its children. Exactly one child equals m; the other child's value is a candidate, since that child's subtree minimum is the largest value that lost to m at this node's subtree boundary. Update best with the smaller of best and the candidate, then move into the child equal to m.

Invariant: after each iteration, best is the minimum over all values defeated by m on the portion of the path walked so far, and tree[i] == m still holds. At termination i is a leaf holding m, so best is the minimum over every value m defeated, which by the claim is s.

Complexity: the loop takes one step per level, so it performs at most height(tree) = O(log n) iterations and O(log n) comparisons after the input is received, using O(1) extra space. It never scans all leaves, which satisfies the stated performance requirement.

Edge cases: n = 2 gives a length-3 tree, the loop runs exactly once and returns the root's non-minimum child. When n is not a power of two the leaves sit at two different depths; the index-based stop condition handles that with no special casing, including the boundary where the minimum sits at index n - 1, the very first leaf, directly under the last internal node n - 2. Negative values and zero need no special handling because only comparisons are used. The winning candidate can appear at the first step, in the middle of the descent, or at the deepest sibling, so every candidate must be compared rather than just the first or the last. All values lie in [-1000000000, 1000000000] and no sum or product is computed, so every intermediate fits in a signed 32-bit integer.

Time complexity:
O(log n)
Space complexity:
O(1)