We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Second Minimum Node In a Binary Tree

Number: 671

Difficulty: Easy

Paid? No

Companies: LinkedIn, Meta

Problem Description

A special binary tree is given where each node has either two children or none. For every internal node, its value is equal to the minimum of its two children. The task is to find the second minimum distinct value in the entire tree. If such a value does not exist, return -1.

Key Insights

  • The root holds the smallest value in the tree.
  • Only nodes with a value larger than the root are candidates for the second minimum.
  • Use depth-first search (DFS) to traverse the tree and update the potential second minimum value.
  • The tree's special property helps eliminate unnecessary comparisons during traversal.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes in the tree. Space Complexity: O(h) where h is the height of the tree (recursive call stack).

Solution

Use a DFS approach to traverse the tree starting from the root. The root's value is established as the smallest value. As you traverse, if a node's value is greater than the root and less than the current candidate for second minimum, you update the candidate. If a node’s value is exactly equal to the smallest value, continue traversing its children. This approach leverages the tree's property to efficiently search for the second smallest unique value. Finally, return the candidate if found, otherwise return -1.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        # The smallest value is at the root.
        self.first = root.val
        self.second = float('inf')
        
        def dfs(node):
            if not node:
                return
            # If node's value is greater than the smallest and less than current second candidate, update second.
            if self.first < node.val < self.second:
                self.second = node.val
            # Continue search only in branches where the candidate might appear.
            elif node.val == self.first:
                dfs(node.left)
                dfs(node.right)
        
        dfs(root)
        # If second remains infinity, no second minimum exists.
        return self.second if self.second < float('inf') else -1
← Back to All Questions