




class  _lowerCAmelCase     :

      def __init__(   self      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  Optional[Any]		       =     val
        lowerCAmelCase__				:  Any		       =     None
        lowerCAmelCase__				:  int		       =     None







      def 	__magic_name__(   self      ,				__UpperCAmelCase		):
        if self.val:
          if val < self.val:
            if self.left is None:
              lowerCAmelCase__				:  Optional[int]		       =     Node(__UpperCAmelCase		)
            else:
              self.left.insert(__UpperCAmelCase		)
          elif val > self.val:
            if self.right is None:
              lowerCAmelCase__				:  Tuple		       =     Node(__UpperCAmelCase		)
            else:
              self.right.insert(__UpperCAmelCase		)
        else:
          lowerCAmelCase__				:  Any		       =     val



def      __lowerCAmelCase			(					UpperCamelCase	,      UpperCamelCase      )     ->	Optional[int]:
  # Recursive traversal
  if root:
    inorder(root.left	,      UpperCamelCase      )
    res.append(root.val      )
    inorder(root.right	,      UpperCamelCase      )



def      __lowerCAmelCase			(					UpperCamelCase      )     ->	Tuple:
  # Build BST
  if len(UpperCamelCase      ) == 0:
    return arr
  lowerCAmelCase__				:  Dict		       =     Node(arr[0]      )
  for i in range(1	,      len(UpperCamelCase      )      ):
    root.insert(arr[i]      )
  # Traverse BST in order.
  lowerCAmelCase__				:  Any		       =     []
  inorder(UpperCamelCase	,      UpperCamelCase      )
  return res


if __name__ == "__main__":
     print(tree_sort([10, 1, 3, 2, 9, 14, 13]))







def      __lowerCAmelCase			(					UpperCamelCase      )     ->	bool:
  if not isinstance(UpperCamelCase	,      UpperCamelCase      ):
    raise ValueError('''Input series is not valid, valid series - [2, 4, 6]'''      )
  if len(UpperCamelCase      ) == 0:
    raise ValueError('''Input list must be a non empty list'''      )
  if len(UpperCamelCase      ) == 1:
    return True
  lowerCAmelCase__				:  Tuple		       =     series[1] - series[0]
  for index in range(len(UpperCamelCase      ) - 1      ):
    if series[index + 1] - series[index] != common_diff:
      return False
  return True



def      __lowerCAmelCase			(					UpperCamelCase      )     ->	float:
  if not isinstance(UpperCamelCase	,      UpperCamelCase      ):
    raise ValueError('''Input series is not valid, valid series - [2, 4, 6]'''      )
  if len(UpperCamelCase      ) == 0:
    raise ValueError('''Input list must be a non empty list'''      )
  lowerCAmelCase__				:  int		       =     0
  for val in series:
    answer += val
  return answer / len(UpperCamelCase      )


if __name__ == "__main__":
     import doctest

     doctest.testmod()

