'''
keys: 
Solutions:
Similar: 783 (the same)
T:
S:
'''
from typing import List


# 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 __init__(self):
        self.res = float("inf")
        self.prev = None 
    
    # in-order traverse, T: O(N). S: O(1)
    def getMinimumDifference(self, root: TreeNode) -> int:
        if not root:
            return self.res
        self.getMinimumDifference(root.left)
        if self.prev != None:
            self.res = min(self.res, root.val - self.prev)
        self.prev = root.val
        self.getMinimumDifference(root.right)
        
        return self.res
    
    # write to array
    # Just the inorder traversal of the entire tree should yield the 
    # sorted order. So the time complexity can be reduced to O(n)
    # T: O(n), n as the number of nodes in the tree, from sorting
    # S: O(n)
    def getMinimumDifference1(self, root: TreeNode) -> int:
        vals = []
        def dfs(node):
            if node:
                dfs(node.left)
                vals.append(node.val)
                dfs(node.right)
                
        dfs(root)
        return min(vals[i+1] - vals[i]
                   for i in range(len(vals) - 1))
    
    # T: O(N), n as the number of nodes in the tree
    # S: O(h), h as the height of tree
    def getMinimumDifference2(self, root: TreeNode) -> int:
        def dfs(node):
            if node:
                dfs(node.left)
                self.ans = min(self.ans, node.val - self.prev)
                self.prev = node.val
                dfs(node.right)

        self.prev = float('-inf')
        self.ans = float('inf')
        dfs(root)
        return self.ans
    
    
node1 = TreeNode(1)
node2 = TreeNode(3)
node1.right = node2
node3 = TreeNode(2)
node2.left = node3
sol = Solution()
sol.getMinimumDifference2(node1)





