We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row.  Each glass holds one cup (250ml) of champagne.

Then, some champagne is poured in the first glass at the top.  When the top most glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it.  When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on.  (A glass at the bottom row has it's excess champagne fall on the floor.)

For example, after one cup of champagne is poured, the top most glass is full.  After two cups of champagne are poured, the two glasses on the second row are half full.  After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now.  After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.



Now after pouring some non-negative integer cups of champagne, return how full the j-th glass in the i-th row is (both i and j are 0 indexed.)

 


Example 1:
Input: poured = 1, query_glass = 1, query_row = 1
Output: 0.0
Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2:
Input: poured = 2, query_glass = 1, query_row = 1
Output: 0.5
Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.


 

Note:


       poured will be in the range of [0, 10 ^ 9].
       query_glass and query_row will be in the range of [0, 99].

Difficulty: interview

Starter code:

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        

Solutions:
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def addValueToList(self, root, lst):
         if root is not None:
             lst.append(root.val)
             self.addValueToList(root.left, lst)
             self.addValueToList(root.right, lst)
 
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         values = []
         self.addValueToList(root, values)
         sorted_values = sorted(values)
         max_diff = sorted_values[-1] - sorted_values[0]
         for i in range(len(values)-1):
             if sorted_values[i+1] - sorted_values[i] < max_diff:
                 max_diff = sorted_values[i+1] - sorted_values[i]
         return max_diff

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def minDiffInBST(self, root):
         min_diff = float('inf')
         curr = root
         stack = []
         last_val = float('inf')
         while stack or curr:
             while curr:
                 stack.append(curr)
                 curr = curr.left
                 
             curr = stack.pop()
             min_diff = min(min_diff, abs(curr.val - last_val))
             last_val = curr.val
             curr = curr.right
             
         return min_diff
                 

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         self.min = float('inf')
         self.prev = None
         self.dfs(root)
         return self.min
     
     def dfs(self, node):
         if not node:
             return
         self.dfs(node.left)
         if self.prev:
             self.min = min(self.min, node.val - self.prev.val)
         self.prev = node
         self.dfs(node.right)
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     prev = float('-inf')
     res = float('inf')
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         if root.left:
             self.minDiffInBST(root.left)
         self.res = min(self.res, root.val-self.prev)
         self.prev = root.val
             
         if root.right:
             self.minDiffInBST(root.right)
         
         return self.res

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 import sys
 
 class Solution:
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         self.res = sys.maxsize;
         self.prevVal = -sys.maxsize;
         
         def in_order(root):
             if not root: return;
             in_order(root.left);
             
             diff = root.val - self.prevVal;
             self.prevVal = root.val
             self.res = min(self.res, diff);
             
             in_order(root.right);
             
         in_order(root);
         return self.res;

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         theValues = []
         def inorder(node):
             if(node!=None):
                 inorder(node.left)
                 theValues.append(node.val)
                 inorder(node.right)
         inorder(root)
         minDiff = sys.maxsize
         for i in range(len(theValues)-1):
             minDiff = min(minDiff, theValues[i+1]-theValues[i])
         return minDiff

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 def dfs(lst, root):
     if root != None:
         lst.append(root.val)
         dfs(lst, root.left)
         dfs(lst, root.right)
 
 class Solution:
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         lst = []
         dfs(lst, root)
         lst.sort()
         res = float('inf')
         for i in range(1, len(lst)):
             res = min(res, lst[i] - lst[i - 1])
         return res
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 import sys
 class Solution:
     def makeList(self,root):
         if root == None:
             return([])
         else:
             return(self.makeList(root.left) + [root.val] + self.makeList(root.right))
         
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         arr = self.makeList(root)
         minDistance = sys.maxsize
         
         if len(arr) == 0:
             return(0)
         else:
             for i in range(1,len(arr)):
                 gap = abs(arr[i] - arr[i-1])
                 if gap < minDistance:
                     minDistance = gap
                     
             return(minDistance)
                 

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 from math import inf
 
 class Solution:
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         if not root:
             return 0
         
         self.ans = inf
         self.dfs(-inf, root, inf)
         return self.ans
     
     def dfs(self, left, root, right):
         self.ans = min(root.val - left, self.ans, right - root.val)
         if root.left:
             self.dfs(left, root.left, root.val)
         
         if root.right:
             self.dfs(root.val, root.right, right)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         vals = self.in_order_traversal(root)
         min_diff = float('inf')
         for i in range(len(vals) - 1):
             min_diff = min(min_diff, vals[i+1] - vals[i])
         return min_diff
         
     def in_order_traversal(self, root):
         vals = []
         if root is not None:
             vals = self.in_order_traversal(root.left) + [root.val] + self.in_order_traversal(root.right)
         return vals

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         def inorder(root):
             if root:
                 yield from inorder(root.left)
                 yield root.val
                 yield from inorder(root.right)
         
         it = inorder(root)
         
         prev = next(it)
         m_ = 1 << 31
         
         while True:
             n = next(it, False)
             if not n:
                 break
             m_ = min(m_, abs(n - prev))
             prev = n
   
         return m_        

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         self.result = []
         
         def insert_node(node):
             if node:
                 self.result.append(node.val)
                 insert_node(node.left)
                 insert_node(node.right)
             else:
                 return
         insert_node(root)
         
         self.result.sort()
         
         minimum = None
         
         for i in range(len(self.result) - 1):
             diff = self.result[i + 1] - self.result[i]
             if not minimum:
                 minimum = diff
             elif minimum > diff:
                 minimum = diff
             if minimum == 0:
                 return minimum
         return minimum
             
         
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         tree = []
         
         def Traversal(node):
             if node != None:
                 Traversal(node.left)
                 tree.append(node.val)
                 Traversal(node.right)
                 
         Traversal(root)
         
         mini = float('inf')
         for i in range(1, len(tree)):
             if abs(tree[i-1]-tree[i]) < mini:
                 mini = abs(tree[i-1]-tree[i])
         return mini

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     
     diff = float('inf')
     prev = float('inf')
     def minDiffInBST(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         self.traversal(root)
         return self.diff
     
     def traversal(self, node):
         
         if node == None:
             return
         
         self.traversal(node.left)
         
         self.diff = min(self.diff, abs(node.val - self.prev))
         self.prev = node.val
          
         
         self.traversal(node.right)
         
     
         
         return