Second Minimum Node In a Binary Tree (671)

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.

Approach 1 : DFS

1. The KEY point of this problem is to observe that this tree's root node's val is always the smallest value.

2. We then use an Array with index 0 being the value at the root.node and index 1 being the location which will store the second smallest value. **Additionnally, I used an Integer object for the array in lieu of a primitive (int) array to avert an error in the advent that the only other element in the tree is Integer.MAX_VALUE. (primitive long array type would have also worked as it can compare numbers that are greater than 31bit like the aforementioned).

3. Upon this fact, we traverse the tree's node recursively and while the node that we're currently visiting does not equal what was at the initial root node(res[0]), we update res[1] to take the smallest node's value that we visit ------- Since the array is passed by reference, we always have have access to res[0] which is subsequently used as an anchor to compare each nodes and make sure they do not equal to the initial root.val.

**(primitive long array type would have also worked to compare Integer.MAX_VALUE has it can store more than 31bits.

Time: O(N) Space: O(1)

class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        Integer[]res = {root.val, null};
        
        findMin(root, res);
        
        return res[1] == null ? -1 : res[1];
    }
    private void findMin(TreeNode root, Integer[]res){
        if(root == null) return;
        
        findMin(root.left, res);
        findMin(root.right, res);
        
        if(root.val != res[0]){
            res[1] = res[1] == null ? root.val : Math.min(res[1], root.val);
        }
    }
}

Approach 2 : BFS

I used a level order traversal and implemented the same logic above. (see 1.3)

class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        Integer secondMin = null;
        
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.val != root.val){
                secondMin = secondMin == null ? node.val : Math.min(secondMin, node.val);
            }
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        return secondMin == null ? -1 : secondMin;
    }
}

Time: O(N) Space: O(N)