LeetCode: 671. Second Minimum Node In a Binary Tree

The Problem

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 the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

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: root = [2,2,5,null,null,5,7]
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Solution

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

int findSecondMinimumValue(TreeNode* root) {
    map<unsigned, unsigned> ordered;
    findSecondMinimumValue(root, ordered);

    if (ordered.size() < 2) return -1;
    auto it = ordered.begin();
    ++it;
    return it->first;
}


void findSecondMinimumValue(TreeNode* root, map<unsigned, unsigned> &ordered) {
    if (root == nullptr) return;

    ordered[root->val] = 1;
    findSecondMinimumValue(root->left, ordered);
    findSecondMinimumValue(root->right, ordered);
}

Let's break it down step by step:

1. The function findSecondMinimumValue takes a pointer to the root node of a binary tree as its parameter and returns an integer value.
2. Inside the findSecondMinimumValue function, a map<unsigned, unsigned> named ordered is declared. A map is a data structure that stores key-value pairs in a sorted order based on the keys. In this case, the map is being used to keep track of the existence of each value encountered in the tree.
3. The main function, findSecondMinimumValue, is then called with the root of the binary tree and the ordered map. This function is responsible for populating the ordered map with the values from the binary tree.
4. The function first checks if the provided root pointer is nullptr, which would indicate an empty subtree. If it's empty, the function simply returns, as there's nothing to process.
5. If the root is not nullptr, the code proceeds to add the value of the current node (root->val) to the ordered map. This step helps keep track of the existence of the values in the tree.
6. The function then recursively calls itself on the left and right children of the current node (root->left and root->right). This recursive process continues until all nodes in the binary tree have been visited.
7. After the findSecondMinimumValue function has processed the entire tree and populated the ordered map with value existences, the main function proceeds.
8. The main function first checks if the size of the ordered map is less than 2. If this is the case, it means there are not enough distinct values in the tree to find a second smallest value. In such a scenario, the function returns -1 to indicate that no second smallest value exists.
9. If the ordered map has at least 2 distinct values, it means there's a possibility of finding a second smallest value. The code obtains an iterator (it) pointing to the beginning of the ordered map and then increments the iterator once using ++it. This is done to move the iterator to the second smallest value in the map.
10. Finally, the function returns the key of the element pointed to by the iterator it, which represents the second smallest value in the binary tree.