code: 
  
  
  '''simple docstring'''
  
  
  
  # This Python program implements an optimal binary search tree (abbreviated BST)
  # building dynamic programming algorithm that delivers O(n^2) performance.
  #
  # The goal of the optimal BST problem is to build a low-cost BST for a
  # given set of nodes, each with its own key and frequency. The frequency
  # of the node is defined as how many time the node is being searched.
  # The search cost of binary search tree is given by this formula:
  #
  # cost(1, n) = sum{i = 1 to n}((depth(node_i) + 1) * node_i_freq)
  #
  # where n is number of nodes in the BST. The characteristic of low-cost
  # BSTs is having a faster overall search time than other implementations.
  # The reason for their fast search time is that the nodes with high
  # frequencies will be placed near the root of the tree while the nodes
  # with low frequencies will be placed near the leaves of the tree thus
  # reducing search time in the most frequent instances.
  import sys
  from random import randint
  
  
  
  
  
  class      UpperCAmelCase_						:
  
  
  
  
  
      """simple docstring"""
  
  
  
  
  
  
      def __init__(							self    ,  SCREAMING_SNAKE_CASE_    ,  SCREAMING_SNAKE_CASE_			)       ->  Any:
           __lowerCamelCase     :			Any              =	key
           __lowerCamelCase     :			str              =	freq
  
  
  
  
  
  
  
      def __str__(							self			)       ->  str:
           return f'Node(key={self.key}, freq={self.freq})'
  
  
  
  
  
  
  
  def     UpperCAmelCase__      (			UpperCAmelCase_					:       Tuple   ,					UpperCAmelCase_					:       Any   ,					UpperCAmelCase_					:       Union[str, Any]   ,					UpperCAmelCase_					:       str   ,					UpperCAmelCase_					:       Tuple   ,					UpperCAmelCase_					:       Optional[int]							)  ->	Optional[int]:
       if i > j or i < 0 or j > len(lowerCAmelCase__							) - 1:
            return
  
       __lowerCamelCase     :			Tuple              =	root[i][j]
       if parent == -1:  # root does not have a parent
            print(F'{key[node]} is the root of the binary search tree.'							)
       elif is_left:
            print(F'{key[node]} is the left child of key {parent}.'							)
       else:
            print(F'{key[node]} is the right child of key {parent}.'							)
  
       print_binary_search_tree(lowerCAmelCase__   ,					lowerCAmelCase__   ,					lowerCAmelCase__   ,					node - 1   ,					key[node]   ,					lowerCAmelCase__							)
       print_binary_search_tree(lowerCAmelCase__   ,					lowerCAmelCase__   ,					node + 1   ,					lowerCAmelCase__   ,					key[node]   ,					lowerCAmelCase__							)
  
  
  
  def     UpperCAmelCase__      (			UpperCAmelCase_					:       str							)  ->	Tuple:
       nodes.sort(key=lambda UpperCAmelCase_							: node.key							)
  
       __lowerCamelCase     :			Dict              =	len(lowerCAmelCase__							)
  
       __lowerCamelCase     :			int              =	[nodes[i].key for i in range(lowerCAmelCase__							)]
       __lowerCamelCase     :			Optional[Any]              =	[nodes[i].freq for i in range(lowerCAmelCase__							)]
  
       # This 2D array stores the overall tree cost (which's as minimized as possible);
       # for a single key, cost is equal to frequency of the key.
       __lowerCamelCase     :			List[Any]              =	[[freqs[i] if i == j else 0 for j in range(lowerCAmelCase__							)] for i in range(lowerCAmelCase__							)]
       # sum[i][j] stores the sum of key frequencies between i and j inclusive in nodes
       # array
       __lowerCamelCase     :			List[Any]              =	[[freqs[i] if i == j else 0 for j in range(lowerCAmelCase__							)] for i in range(lowerCAmelCase__							)]
       # stores tree roots that will be used later for constructing binary search tree
       __lowerCamelCase     :			List[str]              =	[[i if i == j else 0 for j in range(lowerCAmelCase__							)] for i in range(lowerCAmelCase__							)]
  
       for interval_length in range(2   ,					n + 1							):
            for i in range(n - interval_length + 1							):
                 __lowerCamelCase     :			List[Any]              =	i + interval_length - 1
  
                 __lowerCamelCase     :			List[str]              =	sys.maxsize  # set the value to "infinity"
                 __lowerCamelCase     :			str              =	total[i][j - 1] + freqs[j]
  
                 # Apply Knuth's optimization
                 # Loop without optimization: for r in range(i, j + 1):
                 for r in range(root[i][j - 1]   ,					root[i + 1][j] + 1							):  # r is a temporal root
                      __lowerCamelCase     :			Union[str, Any]              =	dp[i][r - 1] if r != i else 0  # optimal cost for left subtree
                      __lowerCamelCase     :			Any              =	dp[r + 1][j] if r != j else 0  # optimal cost for right subtree
                      __lowerCamelCase     :			Any              =	left + total[i][j] + right
  
                      if dp[i][j] > cost:
                           __lowerCamelCase     :			Optional[int]              =	cost
                           __lowerCamelCase     :			List[Any]              =	r
  
       print('Binary search tree nodes:'							)
       for node in nodes:
            print(lowerCAmelCase__							)
  
       print(F'\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}.'							)
       print_binary_search_tree(lowerCAmelCase__   ,					lowerCAmelCase__   ,					0   ,					n - 1   ,					-1   ,					lowerCAmelCase__							)
  
  
  
  def     UpperCAmelCase__      (			)  ->	Optional[Any]:
       # A sample binary search tree
       __lowerCamelCase     :			List[str]              =	[Node(lowerCAmelCase__   ,					randint(1   ,					50							)							) for i in range(10   ,					0   ,					-1							)]
       find_optimal_binary_search_tree(lowerCAmelCase__							)
  
  
  if __name__ == "__main__":
      main()
  
  
  
  
  
  
  
style_context: 
  
  
  '''simple docstring'''
  
  
  
  def     UpperCAmelCase__      (			UpperCAmelCase_					:       str							)  ->	int:
       __lowerCamelCase     :			Tuple              =	str(UpperCAmelCase_							).strip()
       if not bin_string:
            raise ValueError('Empty string was passed to the function'							)
       __lowerCamelCase     :			Optional[int]              =	bin_string[0] == '-'
       if is_negative:
            __lowerCamelCase     :			List[Any]              =	bin_string[1:]
       if not all(char in '01' for char in bin_string							):
            raise ValueError('Non-binary value was passed to the function'							)
       __lowerCamelCase     :			Optional[int]              =	0
       for char in bin_string:
            __lowerCamelCase     :			str              =	2 * decimal_number + int(UpperCAmelCase_							)
       return -decimal_number if is_negative else decimal_number
  
  
  if __name__ == "__main__":
        from doctest import testmod
  
        testmod()
  
  
  
  
  
  
  