O(n) time solution - Accepted


  • 0
    J

    The first minimum is always going to be the first node in the tree as the children will either be equal or bigger. And if a node is encountered whose value is greater or equal to the current second minimum, further traversal is not required. One can write a solution based on this.

    class Solution {
        public int findSecondMinimumValue(TreeNode root) {
            if (root.right == null || root.left == null) {
                return -1;
            }
            int firstMin = root.val;
            int secondMin = helper(root, firstMin, root.left.val > root.right.val ? root.left.val : root.right.val);
            
            return firstMin == secondMin ? -1 : secondMin;
        }
        
        public int helper(TreeNode root, int firstMin, int secondMin) {
            if (root == null || root.val >= secondMin) {
                return secondMin;
            }
            
            int leftMin = Integer.MAX_VALUE, rightMin = Integer.MAX_VALUE;
            int min = secondMin > root.val ? (root.val > firstMin ? root.val : secondMin) : secondMin;
            leftMin = helper(root.left, firstMin, min);
            rightMin = helper(root.right, firstMin, min);
            
            return leftMin > rightMin ? rightMin : leftMin;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.