easy Second Minimum Node In a Binary Tree

Problem Statement

You are given a non-empty special binary tree consisting of nodes with a positive value, where each node in this tree has exactly two or zero children. If the node has two children, then the current node's value is the smaller value among its two children. In other words, the property root.val = min(root.left.val, root.right.val) always holds for each node of the tree.

Given such a binary tree, return the second minimum value in the set made using all the nodes' values in the whole tree. If no such second minimum value exists, output -1 instead.

Examples

Example 1:

• Input: [4, 4, 5, null, null, 5, 6]

• Expected Output: 5
• Justification: The smallest value is 4, and the second smallest is 5.

Example 2:

• Input: [3, 3, 4, null, null, 5, 4, 5, 6, null, null]

• Expected Output: 4
• Justification: The smallest value is 3. The second smallest value, which is distinct from the smallest, is 4.

Example 3:

• Input: [2, 2, 2, null, null, 2, 2]

• Expected Output: -1
• Justification: All values in the tree are the same (2), so there is no second minimum value.

Solution

To solve this problem, we'll traverse the binary tree to find the smallest and second smallest unique values. Since the tree's structure ensures that the root node contains the smallest value, our primary goal is to find the next larger unique value as we explore the tree. We'll use a depth-first search (DFS) strategy for traversal because it allows us to explore each branch of the tree thoroughly before moving to the next branch, making it easier to compare values across different parts of the tree.

Our approach is effective because it leverages the tree's special property, minimizing unnecessary comparisons and ensuring we can find the second minimum value (if it exists) as efficiently as possible. By focusing on depth-first traversal, we're able to keep our search localized and straightforward, reducing the complexity of our solution. This method is particularly well-suited for trees where the second minimum value might be deep within a branch, ensuring we explore all possibilities.

Step-by-Step Algorithm

1. Initialize:

   • Start with the root of the tree. Let firstMin be the value of the root node, as it's guaranteed to be the smallest value in the tree.

2. Define a Recursive Function findSecondMin:

   • This function takes a node and the value of firstMin as arguments.
   • If the node is null, return Integer.MAX_VALUE (or an equivalent large value) to indicate that no valid second minimum value is found in this path.
   • If the node's value is greater than firstMin, return the node's value because it's a potential second minimum.
   • Otherwise, recursively call findSecondMin for both the left and right children of the current node, passing firstMin as an argument.

3. Compare Left and Right:

   • After getting the values from the left and right subtrees (leftMin and rightMin), compare them to find the smaller value that is still greater than firstMin. This comparison ensures we find the second minimum value among all nodes examined.

4. Aggregate Results:

   • The minimum of leftMin and rightMin is the potential second minimum value in the subtree rooted at the current node. Return this value up the call stack.

5. Handle the Root's Result:

   • For the initial call from the root, check if the returned value is Integer.MAX_VALUE. If it is, it means there is no second minimum value in the tree, and you should return -1. Otherwise, return the found value.

Algorithm Walkthrough

Let's walk through the input [3, 3, 4, null, null, 5, 4, 5, 6, null, null], visualizing the tree as:

        3
       / \
      3   4
         / \
        5   4
       / \
      5   6

1. Start at the Root (3):

   • firstMin = 3.

2. Move to the Left Child (3):

   • It's equal to firstMin, so no update. Recursively check its children, but since it has none, it ends this path.

3. Move to the Right Child (4):

   • This value is greater than firstMin, so it's a potential second minimum. Return 4.

4. Conclusion:

   • The algorithm concludes with 4 as the second minimum value, which is the correct answer for the provided tree structure.

Code

// class TreeNode {
//     int val;
//     TreeNode left, right;
//     // Constructor to create a new TreeNode
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  // Main method to find the second minimum value in the binary tree
  public int findSecondMinimumValue(TreeNode root) {
    // Return -1 if root is null indicating tree is empty
    if (root == null) return -1;
    // Find the second minimum value starting from root
    int secondMin = findSecondMin(root, root.val);
    // Check if second minimum value is found; otherwise return -1
    return secondMin < Integer.MAX_VALUE ? secondMin : -1;
  }

  // Helper method to recursively find the second minimum value
  private int findSecondMin(TreeNode node, int firstMin) {
    // Base case: return MAX_VALUE if node is null
    if (node == null) return Integer.MAX_VALUE;
    // If current node's value is greater than firstMin, it's a potential secondMin
    if (node.val > firstMin) return node.val;

    // Recursively find the second min in the left and right subtrees
    int leftMin = findSecondMin(node.left, firstMin);
    int rightMin = findSecondMin(node.right, firstMin);

    // Return the smaller of the two values that are greater than firstMin
    return Math.min(leftMin, rightMin);
  }

  // Main method to execute the program and test the examples
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1 setup and execution
    TreeNode example1 = new TreeNode(4);
    example1.left = new TreeNode(4);
    example1.right = new TreeNode(5);
    example1.right.left = new TreeNode(5);
    example1.right.right = new TreeNode(6);
    System.out.println(
      "Example 1: Expected Output: 5, Actual Output: " +
      solution.findSecondMinimumValue(example1)
    );

    // Example 2 setup and execution
    TreeNode example2 = new TreeNode(3);
    example2.left = new TreeNode(3);
    example2.right = new TreeNode(4);
    example2.right.left = new TreeNode(5);
    example2.right.right = new TreeNode(4);
    example2.right.left.left = new TreeNode(5);
    example2.right.left.right = new TreeNode(6);
    System.out.println(
      "Example 2: Expected Output: 4, Actual Output: " +
      solution.findSecondMinimumValue(example2)
    );

    // Example 3 setup and execution
    TreeNode example3 = new TreeNode(2);
    example3.left = new TreeNode(2);
    example3.right = new TreeNode(2);
    example3.right.left = new TreeNode(2);
    example3.right.right = new TreeNode(2);
    System.out.println(
      "Example 3: Expected Output: -1, Actual Output: " +
      solution.findSecondMinimumValue(example3)
    );
  }
}

Complexity Analysis

• Time Complexity: , where N is the number of nodes in the binary tree. In the worst case, we might have to visit every node in the tree once to determine the second minimum value.
• Space Complexity: , where H is the height of the binary tree. This space is used by the call stack during the recursive depth-first search. In the worst case (a skewed tree), the space complexity can be , but for a balanced tree, it would be .