Problem Description

Given a special kind of binary tree where every node has either 0 or 2 children, and every node's value is a positive integer. Additionally, for every node with two children, the node's value is the smaller of its two children's values. Your task is to find the second minimum value among all the nodes in the tree.

• If such a second minimum value does not exist, return -1.
• The tree will have at least one node.
• All node values are positive integers.
• The root node always contains the minimum value in the tree.

Constraints:

• Each node has either 0 or 2 children.
• All node values are positive integers.
• There may not always be a second minimum value.

Thought Process

The problem is asking us to find the smallest value in the tree that is greater than the root's value. Since the root is always the minimum, we want the next smallest unique value.

A brute-force approach would be to traverse all nodes, collect their values, sort them, and pick the second unique value. However, this does unnecessary work and uses extra space.

Instead, we should leverage the unique property of the tree: the root is always the minimum, and node values propagate this minimum property down. So, any value greater than the root is a candidate for the second minimum. We can avoid storing all values and instead keep track of the smallest candidate we find during traversal.

This leads us to a more efficient solution: traverse the tree, and whenever we find a value greater than the root, check if it's the smallest such value we've seen so far.

Solution Approach

Let's break down the optimized algorithm step by step:

1. Store the root value: Since the root is guaranteed to have the minimum value, we keep this as our baseline.
2. Initialize a variable for the second minimum: We'll use a variable (e.g., second_min) and set it to infinity or -1 initially.
3. Traverse the tree: We can use DFS (Depth-First Search) or BFS (Breadth-First Search) to visit each node.
4. Compare each node's value:
   • If the node's value is greater than the root and less than our current second_min, update second_min.
   • If the node's value equals the root, keep traversing its children, as a second minimum might be lower in the tree.
5. Return the result: After traversal, if second_min was updated, return it; otherwise, return -1.

This approach is efficient because we only consider values greater than the root, and we don't need to store all values or sort them.

Example Walkthrough

Let's consider the following binary tree:

        2
       / \
      2   5
         / \
        5   7
  

• The root value is 2.
• We traverse the tree:
  • Visit left child (2): same as root, keep searching.
  • Visit right child (5): greater than root, set second_min = 5.
  • Visit right child's left (5): same as current second_min, no update.
  • Visit right child's right (7): greater than root and current second_min, but not smaller, so no update.
• After traversal, the smallest value greater than 2 is 5, so return 5.

If there were no values greater than the root, we would return -1.

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(N log N) — traverse all nodes (O(N)), collect values, sort them (O(N log N)).
  • Space Complexity: O(N) — to store all unique values.
• Optimized Approach (DFS/BFS):
  • Time Complexity: O(N) — every node is visited once.
  • Space Complexity: O(H) — where H is the height of the tree (for recursion stack in DFS), or O(W) for BFS (width of the tree).

The optimized approach is preferable for both time and space, especially for large trees.

Code Implementation

# 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: TreeNode) -> int:
        self.ans = float('inf')
        min_val = root.val

        def dfs(node):
            if not node:
                return
            if min_val < node.val < self.ans:
                self.ans = node.val
            elif node.val == min_val:
                dfs(node.left)
                dfs(node.right)
        dfs(root)
        return self.ans if self.ans < float('inf') else -1
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int ans = INT_MAX;
    int min_val;

    void dfs(TreeNode* node) {
        if (!node) return;
        if (node->val > min_val && node->val < ans) {
            ans = node->val;
        } else if (node->val == min_val) {
            dfs(node->left);
            dfs(node->right);
        }
    }

    int findSecondMinimumValue(TreeNode* root) {
        min_val = root->val;
        dfs(root);
        return (ans < INT_MAX) ? ans : -1;
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private long ans = Long.MAX_VALUE;
    private int minVal;

    public int findSecondMinimumValue(TreeNode root) {
        minVal = root.val;
        dfs(root);
        return ans < Long.MAX_VALUE ? (int)ans : -1;
    }

    private void dfs(TreeNode node) {
        if (node == null) return;
        if (node.val > minVal && node.val < ans) {
            ans = node.val;
        } else if (node.val == minVal) {
            dfs(node.left);
            dfs(node.right);
        }
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var findSecondMinimumValue = function(root) {
    let ans = Infinity;
    let minVal = root.val;
    function dfs(node) {
        if (!node) return;
        if (node.val > minVal && node.val < ans) {
            ans = node.val;
        } else if (node.val === minVal) {
            dfs(node.left);
            dfs(node.right);
        }
    }
    dfs(root);
    return ans < Infinity ? ans : -1;
};
      

Summary

The key to solving the "Second Minimum Node In a Binary Tree" problem is recognizing the unique structure of the tree: the root is always the minimum, and any value greater than the root is a candidate for the second minimum. By traversing the tree and tracking the smallest value greater than the root, we can efficiently find the answer in linear time without extra space for storing all values. This approach is elegant and leverages the problem's constraints for an optimal solution.