code: 
  from __future__ import annotations
  
  from queue import Queue
  
  
  def       a			(   a		,	a  ):
  
  
  
  
  			'''simple docstring'''
  
  
  			a ^= b
  			b ^= a
  			a ^= b
  			return a, b
  
  
  def       a			(   a		,	a  ):
  
  
  
  
  			'''simple docstring'''
  
  
  			SCREAMING_SNAKE_CASE    	=   1
  			while (1 << j) < max_node:
  						for i in range(1		,	max_node + 1  ):
  									SCREAMING_SNAKE_CASE    	=   parent[j - 1][parent[j - 1][i]]
  						j += 1
  			return parent
  
  
  def       a			(   a		,	a		,	a		,	a  ):
  
  
  
  
  			'''simple docstring'''
  
  
  			if level[u] < level[v]:
  						SCREAMING_SNAKE_CASE	,       SCREAMING_SNAKE_CASE    	=   swap(a		,	a  )
  			# making depth of u same as depth of v
  			for i in range(18		,	-1		,	-1  ):
  						if level[u] - (1 << i) >= level[v]:
  									SCREAMING_SNAKE_CASE    	=   parent[i][u]
      # at the same depth if u==v that mean lca is found
  			if u == v:
  						return u
  			# moving both nodes upwards till lca in found
  			for i in range(18		,	-1		,	-1  ):
  						if parent[i][u] not in [0, parent[i][v]]:
  									SCREAMING_SNAKE_CASE	,       SCREAMING_SNAKE_CASE    	=   parent[i][u], parent[i][v]
      # returning longest common ancestor of u,v
  			return parent[0][u]
  
  
  def       a			(   a		,	a		,	a		,	a		,	a = 1		,	):
  
  
  
  
  			'''simple docstring'''
  
  
  			SCREAMING_SNAKE_CASE    	=   0
  			SCREAMING_SNAKE_CASE    	=   Queue(maxsize=a  )
  			q.put(a  )
  			while q.qsize() != 0:
  						SCREAMING_SNAKE_CASE    	=   q.get()
  						for v in graph[u]:
  									if level[v] == -1:
  												SCREAMING_SNAKE_CASE    	=   level[u] + 1
  												q.put(a  )
  												SCREAMING_SNAKE_CASE    	=   u
  			return level, parent
  
  
  def       a			(   ):
  
  
  
  
  			'''simple docstring'''
  
  
  			SCREAMING_SNAKE_CASE    	=   13
  			# initializing with 0
  			SCREAMING_SNAKE_CASE    	=   [[0 for _ in range(max_node + 10  )] for _ in range(20  )]
  			# initializing with -1 which means every node is unvisited
  			SCREAMING_SNAKE_CASE    	=   [-1 for _ in range(max_node + 10  )]
  			SCREAMING_SNAKE_CASE    	=   {
  			    1: [2, 3, 4],
  			    2: [5],
  			    3: [6, 7],
  			    4: [8],
  			    5: [9, 10],
  			    6: [11],
  			    7: [],
  			    8: [12, 13],
  			    9: [],
  			    10: [],
  			    11: [],
  			    12: [],
  			    13: [],
  			}
  			SCREAMING_SNAKE_CASE	,       SCREAMING_SNAKE_CASE    	=   breadth_first_search(a		,	a		,	a		,	a		,	1  )
  			SCREAMING_SNAKE_CASE    	=   create_sparse(a		,	a  )
  			print('''LCA of node 1 and 3 is: '''		,	lowest_common_ancestor(1		,	3		,	a		,	a  )  )
  			print('''LCA of node 5 and 6 is: '''		,	lowest_common_ancestor(5		,	6		,	a		,	a  )  )
  			print('''LCA of node 7 and 11 is: '''		,	lowest_common_ancestor(7		,	11		,	a		,	a  )  )
  			print('''LCA of node 6 and 7 is: '''		,	lowest_common_ancestor(6		,	7		,	a		,	a  )  )
  			print('''LCA of node 4 and 12 is: '''		,	lowest_common_ancestor(4		,	12		,	a		,	a  )  )
  			print('''LCA of node 8 and 8 is: '''		,	lowest_common_ancestor(8		,	8		,	a		,	a  )  )
  
  
  if __name__ == "__main__":
  							main()
style_context: 
  import numpy as np
  
  
  
  
  
  class 						lowerCamelCase			:
  
  
  
  
  
  
  
  	def __init__(    self			:Any      ,    lowercase			:List[Any]=5      ,    lowercase			:Optional[Any]=5 )		->			Tuple:
  
  
  
  
  
  
  
  				"""simple docstring"""
  
  
  
  
  
  
  				SCREAMING_SNAKE_CASE    	=   depth
  				SCREAMING_SNAKE_CASE    	=   0
  				SCREAMING_SNAKE_CASE    	=   None
  				SCREAMING_SNAKE_CASE    	=   None
  				SCREAMING_SNAKE_CASE    	=   min_leaf_size
  				SCREAMING_SNAKE_CASE    	=   None
  
  
  
  
  
  
  
  	def    snake_case__    (    self			:str      ,    lowercase			:int      ,    lowercase			:int )		->			str:
  
  
  
  
  
  
  
  				"""simple docstring"""
  
  
  
  
  
  
  				if labels.ndim != 1:
  							print('''Error: Input labels must be one dimensional''' )
  
  				return np.mean((labels - prediction) ** 2 )
  
  
  
  
  
  
  
  	def    snake_case__    (    self			:Union[str, Any]      ,    lowercase			:int      ,    lowercase			:Dict )		->			Tuple:
  
  
  
  
  
  
  
  				"""simple docstring"""
  
  
  
  
  
  
  				if x.ndim != 1:
  							print('''Error: Input data set must be one dimensional''' )
  							return
  				if len(lowercase ) != len(lowercase ):
  							print('''Error: X and y have different lengths''' )
  							return
  				if y.ndim != 1:
  							print('''Error: Data set labels must be one dimensional''' )
  							return
  
  				if len(lowercase ) < 2 * self.min_leaf_size:
  							SCREAMING_SNAKE_CASE    	=   np.mean(lowercase )
  							return
  
  				if self.depth == 1:
  							SCREAMING_SNAKE_CASE    	=   np.mean(lowercase )
  							return
  
  				SCREAMING_SNAKE_CASE    	=   0
  				SCREAMING_SNAKE_CASE    	=   self.mean_squared_error(lowercase      ,    np.mean(lowercase ) ) * 2
  				for i in range(len(lowercase ) ):
  							if len(x[:i] ) < self.min_leaf_size:
  										continue
  							elif len(x[i:] ) < self.min_leaf_size:
  										continue
  							else:
  										SCREAMING_SNAKE_CASE    	=   self.mean_squared_error(x[:i]      ,    np.mean(y[:i] ) )
  										SCREAMING_SNAKE_CASE    	=   self.mean_squared_error(x[i:]      ,    np.mean(y[i:] ) )
  										SCREAMING_SNAKE_CASE    	=   error_left + error_right
  										if error < min_error:
  													SCREAMING_SNAKE_CASE    	=   i
  													SCREAMING_SNAKE_CASE    	=   error
  
  				if best_split != 0:
  							SCREAMING_SNAKE_CASE    	=   x[:best_split]
  							SCREAMING_SNAKE_CASE    	=   y[:best_split]
  							SCREAMING_SNAKE_CASE    	=   x[best_split:]
  							SCREAMING_SNAKE_CASE    	=   y[best_split:]
  
  							SCREAMING_SNAKE_CASE    	=   x[best_split]
  							SCREAMING_SNAKE_CASE    	=   DecisionTree(
  							    depth=self.depth - 1      ,    min_leaf_size=self.min_leaf_size )
  							SCREAMING_SNAKE_CASE    	=   DecisionTree(
  							    depth=self.depth - 1      ,    min_leaf_size=self.min_leaf_size )
  							self.left.train(lowercase      ,    lowercase )
  							self.right.train(lowercase      ,    lowercase )
  				else:
  							SCREAMING_SNAKE_CASE    	=   np.mean(lowercase )
  
  				return
  
  
  
  
  
  
  
  	def    snake_case__    (    self			:Optional[int]      ,    lowercase			:List[Any] )		->			str:
  
  
  
  
  
  
  
  				"""simple docstring"""
  
  
  
  
  
  
  				if self.prediction is not None:
  							return self.prediction
  				elif self.left or self.right is not None:
  							if x >= self.decision_boundary:
  										return self.right.predict(lowercase )
  							else:
  										return self.left.predict(lowercase )
  				else:
  							print('''Error: Decision tree not yet trained''' )
  							return None
  
  
  
  
  
  class 						lowerCamelCase			:
  
  
  
  
  
  
  
  	@staticmethod
  	def    snake_case__    (    lowercase			:Optional[int]      ,    lowercase			:Optional[Any] )		->			Dict:
  
  
  
  
  
  
  
  				"""simple docstring"""
  
  
  
  
  
  
  				SCREAMING_SNAKE_CASE    	=   float(0 )
  				for label in labels:
  							squared_error_sum += (label - prediction) ** 2
  
  				return float(squared_error_sum / labels.size )
  
  
  
  def       a			(   )    ->Any:
  
  
  
  
  			'''simple docstring'''
  
  
  			SCREAMING_SNAKE_CASE    	=   np.arange(-1.0		,	1.0		,	0.0_05  )
  			SCREAMING_SNAKE_CASE    	=   np.sin(a  )
  
  			SCREAMING_SNAKE_CASE    	=   DecisionTree(depth=10		,	min_leaf_size=10  )
  			tree.train(a		,	a  )
  
  			SCREAMING_SNAKE_CASE    	=   (np.random.rand(10  ) * 2) - 1
  			SCREAMING_SNAKE_CASE    	=   np.array([tree.predict(a  ) for x in test_cases]  )
  			SCREAMING_SNAKE_CASE    	=   np.mean((predictions - test_cases) ** 2  )
  
  			print('''Test values: ''' + str(a  )  )
  			print('''Predictions: ''' + str(a  )  )
  			print('''Average error: ''' + str(a  )  )
  
  
  if __name__ == "__main__":
  							main()
  							import doctest
  
  							doctest.testmod(name='mean_squarred_error', verbose=True)