Second Minimum Node In a Binary Tree

• LeetCode: Second Minimum Node In a Binary Tree

• 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.

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.

• Examples:

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.

• Analysis:

The value of root is the minimal value of the tree.

The second minimum value is under node(i) value < minimal condition.

When we traverse this tree, we can stop on the following two cases:

    1. null node

    2. the value of current node is bigger than the minival value

• Code - Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        int val = helper(root, root.val);
        if (val == Integer.MAX_VALUE) {
            return -1;
        }
        return val;
    }
    private int helper(TreeNode node, int minVal) {
        if (node == null) {
            return Integer.MAX_VALUE;
        }
        if (node.val > minVal) {
            return node.val;
        }
        int left = helper(node.left, minVal);
        int right = helper(node.right, minVal);
        return Math.min(left, right);
    }
}

• Code - C++:

/**
 * 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 findSecondMinimumValue(TreeNode* root) {
        if (root == NULL) {
            return -1;
        }
        int val = helper(root, root->val);
        if (val == INT_MAX) {
            return -1;
        }
        return val;
    }
    int helper(TreeNode* node, int minVal) {
        if (node == NULL) {
            return INT_MAX;
        }
        if (node->val > minVal) {
            return node->val;
        }
        int left = helper(node->left, minVal);
        int right = helper(node->right, minVal);
        return min(left, right);
    }
};

• Code - Python:

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

class Solution(object):
    INT_MAX = 2 ** 31 - 1
    def findSecondMinimumValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return -1
        val = self.helper(root, root.val)
        if val == self.INT_MAX:
            return -1
        return val
    def helper(self, node, minVal):
        if node == None:
            return self.INT_MAX
        if node.val > minVal:
            return node.val
        left = self.helper(node.left, minVal)
        right = self.helper(node.right, minVal)
        return min(left, right)

• Time Complexity: O(N), N is the node of the length