Leetcode 671. Second Minimum Node In a Binary Tree

Problem Explanation:

The problem provides a special type of binary tree. In this tree, every non-leaf node's value is the smaller value of its two children's values. Your task is to find the second smallest value in the tree.

Take for instance, the following example:

Example 1:

1
2
3 Input:
4     2
5    / \
6   2   5
7      / \
8     5   7

Output: 5

The smallest value in the tree is '2' and the second smallest value is '5'.

Let's also consider a scenario where there isn't a second smallest value:

Example 2:

1
2
3Input:
4    2
5   / \
6  2   2

Output: -1

Here, all nodes have the same value '2'. There is no second smallest value, thus we return -1.

Solution Approach:

The given solution uses recursive depth-first search (DFS) to traverse the binary tree. Here are the steps of the algorithm:

1. If the tree is empty, we return -1.
2. If the value of the root node is greater than the current minimum value, we return the root's value. This is because we are sure that all values in this subtree are greater than the current minimum value (since it is a special binary tree where each node is the minimum of its children)
3. Otherwise, we recursively find the second minimum value in the left and right subtrees, and return the smaller one.

Let's illustrate this with the first example:

1
2
3Start with min_val = root.val = 2
4
5Search in the left subtree:
6- root.val = 2 is not greater than min_val = 2. Continue search in its children:
7  - The left child is null, return -1
8  - The right child is null, return -1
9- The second minimum in the left subtree is max(-1, -1) = -1
10
11Search in the right subtree:
12- root.val = 5 is greater than min_val = 2. Return 5.
13
14The second minimum in the tree is the minimum of -1 and 5, which is 5.

Python Solution:

1
2python
3class Solution:
4    def findSecondMinimumValue(self, root):
5        if root is None:
6            return -1
7        return self.helper(root, root.val)
8
9    def helper(self, root, min_val):
10        if root is None:
11            return -1
12        if root.val > min_val:
13            return root.val
14        
15        left = self.helper(root.left, min_val)
16        right = self.helper(root.right, min_val)
17        
18        if left == -1 or right == -1:
19            return max(left, right)
20        return min(left, right)

Java Solution:

1
2java
3public class Solution {
4    public int findSecondMinimumValue(TreeNode root) {
5        if (root == null) return -1;
6        return findSecondMin(root, root.val);
7    }
8
9    private int findSecondMin(TreeNode root, int minVal) {
10        if (root == null) return -1;
11        if (root.val > minVal) return root.val;
12        
13        int left = findSecondMin(root.left, minVal);
14        int right = findSecondMin(root.right, minVal);
15
16        if (left == -1 || right == -1) return Math.max(left, right);
17        return Math.min(left, right);
18    }
19}

JavaScript Solution:

1
2javascript
3function findSecondMinimumValue(root) {
4    if (!root)
5        return -1;
6    return findSecondMin(root, root.val);
7}
8
9function findSecondMin(node, minVal) {
10    if (!node)
11        return -1;
12    if (node.val > minVal)
13        return node.val;
14
15    let left = findSecondMin(node.left, minVal);
16    let right = findSecondMin(node.right, minVal);
17
18    return left === -1 || right === -1 ?
19        Math.max(left, right) : Math.min(left, right);
20}

C++ Solution:

1
2c++
3class Solution {
4public:
5    int findSecondMinimumValue(TreeNode* root) {
6        if (root == nullptr) return -1;
7        return findSecondMin(root, root->val);
8    }
9
10private:
11    int findSecondMin(TreeNode* root, int min_val) {
12        if (root == nullptr) return -1;
13        if (root->val > min_val) return root->val;
14        
15        int left = findSecondMin(root->left, min_val);
16        int right = findSecondMin(root->right, min_val);
17        
18        return left == -1 || right == -1 ? 
19            max(left, right) : min(left, right);
20    }
21};

C# Solution:

1
2csharp
3public class Solution {
4    public int FindSecondMinimumValue(TreeNode root) {
5        if (root == null) return -1;
6        return FindSecondMin(root, root.val);
7    }
8
9    private int FindSecondMin(TreeNode root, int minVal) {
10        if (root == null) return -1;
11        if (root.val > minVal) return root.val;
12        
13        int left = FindSecondMin(root.left, minVal);
14        int right = FindSecondMin(root.right, minVal);
15
16        return left == -1 || right == -1 ?
17            Math.Max(left, right) : Math.Min(left, right);
18    }
19}

Each recursive function call traverses a branch of the tree. The base cases either capture a null node (no child exists) or the second smallest value (root's value > current min value). Finally, the helper function compares the results of the left and right subtree and returns the lesser of the two (to uphold the property of the smaller value among two sub-nodes). Rust Solution:

1
2rust
3impl Solution {
4    pub fn find_second_minimum_value(root: Option<Rc<RefCell<TreeNode>>>)-> i32 {
5        Solution::find_second_min(root, root.unwrap().borrow().val)
6    }
7
8    fn find_second_min(node: Option<Rc<RefCell<TreeNode>>>, min_val: i32) -> i32 {
9        match node {
10            Some(n) => {
11                let n = n.borrow();
12                if n.val > min_val {
13                    return n.val;
14                }
15
16                let left = Solution::find_second_min(n.left.clone(), min_val);
17                let right = Solution::find_second_min(n.right.clone(), min_val);
18
19                if left == -1 || right == -1 {
20                    return std::cmp::max(left, right);
21                } else {
22                    return std::cmp::min(left, right);
23                }
24            },
25            None => -1
26        }
27    }
28}

In the Rust solution, we defined two methods find_second_minimum_value and find_second_min. It uses Rust's Option and match statement to handle potential null values. The function find_second_min behaves exactly as the helper functions in previous solutions.

Scala Solution:

1
2scala
3class TreeNode(var _value: Int) {
4    var value: Int = _value
5    var left: TreeNode = null
6    var right: TreeNode = null
7}
8
9
10object Solution {
11    def findSecondMinimumValue(root: TreeNode): Int = {
12        if (root == null) -1
13        else findSecondMin(root, root.value)
14    }
15
16    def findSecondMin(node: TreeNode, minVal: Int): Int = {
17        if (node == null) -1
18        else if (node.value > minVal) node.value
19        else {
20            val left = findSecondMin(node.left, minVal)
21            val right = findSecondMin(node.right, minVal)
22
23            if (left == -1 || right == -1) Math.max(left, right)
24            else Math.min(left, right)
25        }
26    }
27}

The Scala solution follows similar process: we define two methods findSecondMinimumValue and findSecondMin. Scala's type inference allows us to leave out the return type of these methods. The patterns in Scala allow us to handle each case (null, greater than minimum value, other) separately but succinctly.

All of these solutions use a depth-first search strategy to traverse the tree, and a helper function to compare the results of the left and right subtree and return the lesser of the two, thereby maintaining the property of the smaller value among two sub-nodes.