# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        """
        tc O(N) sc O(N)
        main idea: keep recursion until find current node.val < root.val
        because if we find node.val > root.val, node's sub nodes is no more than node.val.  hence the second smallest is possible node.val
        but since we have left and right sub nodes, we need to try both path out 
        """
        res = [float('inf')] # cache the second small val as global varible 
        def dfs(node):
            if not node:
                return
            # when current node is smaller than res[0], update   test case:[1,1,3,1,1,3,4,3,1,1,1,3,8,4,8,3,3,1,6,2,1]
            if root.val < node.val < res[0] :
                #print(node.val,res[0])
                res[0] = node.val
                # optimization : early stopping, since if current node.val is bigger than res[0], its children will all be no less than current node.val  
                return
            else:
            #elif node.val == root.val:
                
                dfs(node.right)
                dfs(node.left)
        dfs(root)
        return res[0] if res[0] != float('inf') else -1