Second Minimum Node In a Binary Tree — LeetCode 671

Difficulty: Easy; Category: Tree

Second Minimum Node In a Binary Tree - LeetCode

According to the question description, this special binary tree root is with particular nodes that each node has two or zero sub-node and this node will be always smaller or equal to sub-nodes. And our aim is to find the second minimum node in this tree.

Since the parent node is always smaller or equal to its’ child node, we can consider the root node of the binary tree root will be the smallest one. Then we just need to find the one which is just bigger than the root node.

Solution

class Solution:
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        self.min2 = float('inf')
        min1 = root.val

        def dfs(node):
            if node:
                if min1 < node.val < self.min2:
                    self.min2 = node.val
                elif node.val == min1:
                    dfs(node.left)
                    dfs(node.right)

        dfs(root)
        return self.min2 if self.min2 < float('inf') else -1

1. use float(‘inf’) to initialize our answer self.min2
2. as we mentioned above, assign root.val as the tree root’s minimum value: min1 = root.val
3. dfs goes to each node to check whether the current node value is greater than min1 and less than self.min2. If it is, it means the node is the current second minimum. Assign this node value as our self.min2. And since we know that this node’s children will be always the same or larger than it, continuing this dfs is impossible to find a value between current min1 and self.min2, so we could stop this dfs here
4. If the current node value is equal to min1 , we go through its left node and right node to check if their node value could be the second minimum value
5. If the current node value is bigger than the current self.min2 , it will impossible to be the second minimum value, so just skip processing of this condition
6. If the node of dfs(node) is None, it means we reach the end of the tree root, we could stop the dfs.
7. return self.min2 if we found the second minimum value during the dfs, otherwise, return -1 that says there isn’t any second minimum value

REFERENCE
https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/discuss/107228/Python-Straightforward-with-Explanation