code: 
  
  
  
  # 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        lowerCAmelCase_	:
         def __init__(    self,    SCREAMING_SNAKE_CASE_,    SCREAMING_SNAKE_CASE_ )  ->	int:
            UpperCamelCase					:						Optional[int]					=			key
            UpperCamelCase					:						Any					=			freq
  
  
  
  
  
  
         def __str__(    self )  ->	List[Any]:
            return F"""Node(key={self.key}, freq={self.freq})"""
  
  
  
  
  
  
  def 	UpperCamelCase			(     snake_case__ :					List[str] ,  snake_case__ :					Any ,  snake_case__ :					Union[str, Any] ,  snake_case__ :					Union[str, Any] ,  snake_case__ :					int ,  snake_case__ :					Tuple			)			->  List[str]:
     if i > j or i < 0 or j > len(snake_case__			) - 1:
        return
  
     UpperCamelCase					:						str					=			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(snake_case__ ,  snake_case__ ,  snake_case__ ,  node - 1 ,  key[node] ,  snake_case__			)
     print_binary_search_tree(snake_case__ ,  snake_case__ ,  node + 1 ,  snake_case__ ,  key[node] ,  snake_case__			)
  def 	UpperCamelCase			(     snake_case__ :					int			)			->  Optional[int]:
     nodes.sort(key=lambda snake_case__			: node.key			)
  
     UpperCamelCase					:						Optional[Any]					=			len(snake_case__			)
  
     UpperCamelCase					:						int					=			[nodes[i].key for i in range(snake_case__			)]
     UpperCamelCase					:						Union[str, Any]					=			[nodes[i].freq for i in range(snake_case__			)]
  
     # 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.
     UpperCamelCase					:						Tuple					=			[[freqs[i] if i == j else 0 for j in range(snake_case__			)] for i in range(snake_case__			)]
     # sum[i][j] stores the sum of key frequencies between i and j inclusive in nodes
     # array
     UpperCamelCase					:						List[str]					=			[[freqs[i] if i == j else 0 for j in range(snake_case__			)] for i in range(snake_case__			)]
     # stores tree roots that will be used later for constructing binary search tree
     UpperCamelCase					:						Optional[Any]					=			[[i if i == j else 0 for j in range(snake_case__			)] for i in range(snake_case__			)]
  
     for interval_length in range(2 ,  n + 1			):
        for i in range(n - interval_length + 1			):
           UpperCamelCase					:						Union[str, Any]					=			i + interval_length - 1
  
           UpperCamelCase					:						Dict					=			sys.maxsize  # set the value to "infinity"
           UpperCamelCase					:						int					=			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
              UpperCamelCase					:						Optional[Any]					=			dp[i][r - 1] if r != i else 0  # optimal cost for left subtree
              UpperCamelCase					:						List[str]					=			dp[r + 1][j] if r != j else 0  # optimal cost for right subtree
              UpperCamelCase					:						Optional[Any]					=			left + total[i][j] + right
  
              if dp[i][j] > cost:
                 UpperCamelCase					:						Tuple					=			cost
                 UpperCamelCase					:						Optional[int]					=			r
  
     print('Binary search tree nodes:'			)
     for node in nodes:
        print(snake_case__			)
  
     print(F"""\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}."""			)
     print_binary_search_tree(snake_case__ ,  snake_case__ ,  0 ,  n - 1 ,  -1 ,  snake_case__			)
  def 	UpperCamelCase			(     )			->  Optional[int]:
     # A sample binary search tree
     UpperCamelCase					:						Dict					=			[Node(snake_case__ ,  randint(1 ,  50			)			) for i in range(10 ,  0 ,  -1			)]
     find_optimal_binary_search_tree(snake_case__			)
  
  
  if __name__ == "__main__":
      main()
  
  
  
  
style_context: 
  
  
  
  from __future__ import annotations
  
  import sys
  def 	UpperCamelCase			(     snake_case__ :					int ,  snake_case__ :					int			)			->  tuple[int, int]:
     # base cases
     if abs(snake_case__			) == 1:
        return a, 0
     elif abs(snake_case__			) == 1:
        return 0, b
  
     UpperCamelCase			,  UpperCamelCase					:						Dict					=			a, b
     UpperCamelCase			,  UpperCamelCase					:						int					=			1, 0
     UpperCamelCase			,  UpperCamelCase					:						Union[str, Any]					=			0, 1
  
     while remainder != 0:
        UpperCamelCase					:						str					=			old_remainder // remainder
        UpperCamelCase			,  UpperCamelCase					:						Union[str, Any]					=			remainder, old_remainder - quotient * remainder
        UpperCamelCase			,  UpperCamelCase					:						List[Any]					=			coeff_a, old_coeff_a - quotient * coeff_a
        UpperCamelCase			,  UpperCamelCase					:						Optional[Any]					=			coeff_b, old_coeff_b - quotient * coeff_b
  
     # sign correction for negative numbers
     if a < 0:
        UpperCamelCase					:						Dict					=			-old_coeff_a
     if b < 0:
        UpperCamelCase					:						Any					=			-old_coeff_b
  
     return old_coeff_a, old_coeff_b
  def 	UpperCamelCase			(     )			->  Tuple:
     if len(sys.argv			) < 3:
        print('2 integer arguments required'			)
        return 1
     UpperCamelCase					:						Union[str, Any]					=			int(sys.argv[1]			)
     UpperCamelCase					:						Optional[int]					=			int(sys.argv[2]			)
     print(extended_euclidean_algorithm(snake_case__ ,  snake_case__			)			)
     return 0
  
  
  if __name__ == "__main__":
      raise SystemExit(main())
  
  
  
  