Second-Smallest Distinct Value in a Min-Heap Tree
Updated
Problem statement
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) → intExamples
Example 1
root = [1,1,4,1,3,6,5]return = 3The 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 = -1Every value is 7, so there is only one distinct value. The answer is -1.
Example 3
root = [4,9,6,9,10]return = 6The 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
1and3000nodes. 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