Second Minimum Node In a Binary Tree

Output the second minimum value in the set made of all the nodes’ value in the whole tree.

Question

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is not bigger than its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example:

Input: 
    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.


Input: 
    2
   / \
  2   2

Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.

Analyzation

Queue

Challenge 1: Using only 1 queue to implement it.

Challenge 2: Use BFS algorithm to do it.

IMPORTANT PATTERN!!

All binary tree problem that relates to “LEVEL” or “DEPTH”, or “MINIMUM Node”, or “MAXIMUM Node”, can use this pattern.

Use the queue structure is enough because deque is for both ends.

Note that the nodes can be duplicated so a set is necessary for this problem.

The Code

class Solution:
    """
    @param root: the root
    @return: the second minimum value in the set made of all the nodes' value in the whole tree
    """
    def findSecondMinimumValue(self, root):
        # Write your code here
        if root is None:
            return -1
        
        result_list = []
        queue = [root]
        
        while queue:
            node = queue.pop(0)
            result_list.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        result_list = list(set(result_list))
        result_list.sort()

        if len(result_list) <= 1:
            return -1
        else:
            return result_list[1]

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).