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 							__snake_case    :
  
  
  
  
  
  	def __init__(		self			,					UpperCamelCase_			,					UpperCamelCase_		)			->		Optional[Any]:
  		snake_case__  					=      key
  		snake_case__  					=      freq
  
  
  
  
  
  	def __str__(		self		)			->		str:
  		return F'''Node(key={self.key}, freq={self.freq})'''
  
  
  
  
  
  def 	__lowerCamelCase (  UpperCAmelCase_				,							UpperCAmelCase_				,							UpperCAmelCase_				,							UpperCAmelCase_				,							UpperCAmelCase_				,							UpperCAmelCase_       )      ->Any:
  	if i > j or i < 0 or j > len(UpperCAmelCase_       ) - 1:
  		return
  
  	snake_case__  					=      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(UpperCAmelCase_				,							UpperCAmelCase_				,							UpperCAmelCase_				,							node - 1				,							key[node]				,							UpperCAmelCase_       )
  	print_binary_search_tree(UpperCAmelCase_				,							UpperCAmelCase_				,							node + 1				,							UpperCAmelCase_				,							key[node]				,							UpperCAmelCase_       )
  
  
  
  
  def 	__lowerCamelCase (  UpperCAmelCase_       )      ->Union[str, Any]:
  	nodes.sort(key=lambda UpperCAmelCase_       : node.key       )
  
  	snake_case__  					=      len(UpperCAmelCase_       )
  
  	snake_case__  					=      [nodes[i].key for i in range(UpperCAmelCase_       )]
  	snake_case__  					=      [nodes[i].freq for i in range(UpperCAmelCase_       )]
  
  	# 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.
  	snake_case__  					=      [[freqs[i] if i == j else 0 for j in range(UpperCAmelCase_       )] for i in range(UpperCAmelCase_       )]
  	# sum[i][j] stores the sum of key frequencies between i and j inclusive in nodes
  	# array
  	snake_case__  					=      [[freqs[i] if i == j else 0 for j in range(UpperCAmelCase_       )] for i in range(UpperCAmelCase_       )]
  	# stores tree roots that will be used later for constructing binary search tree
  	snake_case__  					=      [[i if i == j else 0 for j in range(UpperCAmelCase_       )] for i in range(UpperCAmelCase_       )]
  
  	for interval_length in range(2				,							n + 1       ):
  		for i in range(n - interval_length + 1       ):
  			snake_case__  					=      i + interval_length - 1
  
  			snake_case__  					=      sys.maxsize  # set the value to "infinity"
  			snake_case__  					=      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
  				snake_case__  					=      dp[i][r - 1] if r != i else 0  # optimal cost for left subtree
  				snake_case__  					=      dp[r + 1][j] if r != j else 0  # optimal cost for right subtree
  				snake_case__  					=      left + total[i][j] + right
  
  				if dp[i][j] > cost:
  					snake_case__  					=      cost
  					snake_case__  					=      r
  
  	print('Binary search tree nodes:'       )
  	for node in nodes:
  		print(UpperCAmelCase_       )
  
  	print(f'''\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}.'''       )
  	print_binary_search_tree(UpperCAmelCase_				,							UpperCAmelCase_				,							0				,							n - 1				,							-1				,							UpperCAmelCase_       )
  
  
  
  
  def 	__lowerCamelCase (  )      ->Union[str, Any]:
  	# A sample binary search tree
  	snake_case__  					=      [Node(UpperCAmelCase_				,							randint(1				,							50       )       ) for i in range(10				,							0				,							-1       )]
  	find_optimal_binary_search_tree(UpperCAmelCase_       )
  
  
  if __name__ == "__main__":
  			main()
  
  
  
  
style_context: 
  
  
  
  
  
  '''simple docstring'''
  
  
  
  
  from typing import Callable
  
  
  
  
  def 	__lowerCamelCase (  UpperCAmelCase_       )      ->str:
  
  	def wrapper(UpperCAmelCase_       ):
  		snake_case__  					=      function_with_docstring.__doc__
  		return target_function
  
  	return wrapper
  
  
  
  