FastPrepSecond-Smallest Distinct Value in a Min-Heap Tree
Problems/Second-Smallest Distinct Value in a Min-Heap Tree

Second-Smallest Distinct Value in a Min-Heap Tree

DocuSign logoDocuSign● EasyINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A report from March 2019 describes the third round of an onsite. The task is to find the second-smallest value in a min-heap that is stored as a binary tree, where values can repeat. The candidate got stuck and did not finish.

The report does not say whether a repeated smallest value counts as the second smallest, or what to return when there is no second value. It gives no limits or examples. Here, copies of the smallest value do not count. You return the smallest value that is strictly greater than the root's value, or -1 if there is none. The tree is a complete min-heap with 1 to 3,000 nodes and values from 0 to 10^9. We wrote the examples.

Our version is about 85% the same as the reported question.

You are given the root of a binary tree that stores a min-heap. In a min-heap, every node's value is less than or equal to the values of its children, so the root holds the smallest value. Values may repeat.

Return the second-smallest distinct value in the tree: the smallest value that is strictly greater than the root's value. Copies of the smallest value do not count. If every node has the same value, return -1.

Function

secondSmallestDistinct(root: TreeNode) → int

Examples

Example 1

root = [1,1,4,1,3,6,5]return = 3
root
1113465

The smallest value is 1, and it appears three times. The values are 1, 1, 4, 1, 3, 6 and 5, so the distinct values in order are 1, 3, 4, 5, 6. The second-smallest distinct value is 3. It sits under the second 1, not right under the root.

Example 2

root = [7,7,7]return = -1
root
777

Every value is 7, so there is only one distinct value. The answer is -1.

Example 3

root = [4,9,6,9,10]return = 6
root
499106

The distinct values in order are 4, 6, 9, 10. The second smallest is 6, the right child of the root.

Constraints

  • The tree has between 1 and 3000 nodes.
  • 0 <= node.val <= 10^9
  • Every node's value is less than or equal to the values of its children.
  • The tree is complete: every level is full except possibly the last, and the last level is filled from the left.

More DocuSign Onsite Interview questions

  • Count Binary SubstringsONSITE INTERVIEW · Seen Sep 2026
  • Two Positions That Add Up to a TargetPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Compress Consecutive Integer RangesONSITE INTERVIEW · Seen Aug 2026
  • JSON Schema Object ValidatorONSITE INTERVIEW · Seen Aug 2026
  • Most Transactions Kept Without Going NegativeONSITE INTERVIEW · Seen May 2025
  • Three-Part Splits With a Light MiddleONSITE INTERVIEW · Seen May 2025
  • Combine Two Sorted Lists Into OneONSITE INTERVIEW · Seen Apr 2022
  • Exact Palindrome CheckPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
  • Paired Words That Share a SubstringONSITE INTERVIEW · Seen Apr 2022
  • Reverse the Characters of a TextPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022

Similar questions at other companies

  • Count One-Valued Regions in a Binary TreeGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
  • Maximum Depth of Binary TreeLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
  • Path SumSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Binary Tree Preorder TraversalAnduril · ONSITE INTERVIEWAnduril interview questions
  • Root-to-Node Path in a Binary TreeAmazon · ONSITE INTERVIEW
  • Symmetric Binary TreeFigma · ONSITE INTERVIEWFigma interview questions
  • Tree Level with the Most NodesBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
  • Diameter of a Binary TreeMeta · ONSITE INTERVIEWMeta interview questions
  • Check That Every Node Equals Its Descendant SumMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Mirror Image Binary TreesExpedia · ONSITE INTERVIEWExpedia interview questions

Interview reports that mention this question

  • DocuSign SWE Intern Interviews: 27 Experiences (Part 2 of 2)

DocuSign interview experiences

  • DocuSign SWE Intern OA Questions: 53 Experiences (Part 1 of 2)
All DocuSign interview questionsSee DocuSign hiring insights
Saved
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int secondSmallestDistinct(TreeNode root) {
        // Write your code here.
    }
}
Checking account…