Second Minimum Node In a Binary Tree

Intuition

This problem could be solved by DFS.

Notice that, this is just a general binary tree (not a binary search tree). So we should keep update 2 variable smallest and second_smallest while traversal this tree.

Also, another point here is to init the 2 variables to float('inf') so that we don't need to handle with edge cases.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        self.smallest = float('inf')
        self.second_smallest = float('inf')
        self._dfs(root)
        return -1 if self.second_smallest == float('inf') else self.second_smallest

    def _dfs(self, node):
        if node is None:
            return
        if node.val < self.second_smallest:
            if node.val > self.smallest:
                self.second_smallest = node.val
            elif node.val < self.smallest:
                self.smallest, self.second_smallest = node.val, self.smallest
        self._dfs(node.right)
        self._dfs(node.left)