




"""simple docstring"""







from __future__ import annotations




class       lowerCAmelCase__       :


				"""simple docstring"""





				def __init__(     self					:	List[Any]    ,   lowercase__					:	int						):
						__lowercase				:		int												=				data
						__lowercase				:		Node | None												=				None
						__lowercase				:		Node | None												=				None





def 						snake_case__       (					_lowerCamelCase				)			->None:  # In Order traversal of the tree






		"""simple docstring"""


		if tree:
				display(tree.left				)
				print(tree.data				)
				display(tree.right				)

def 						snake_case__       (					_lowerCamelCase				)			->int:






		"""simple docstring"""


		return 1 + max(depth_of_tree(tree.left				),  depth_of_tree(tree.right				)				) if tree else 0

def 						snake_case__       (					_lowerCamelCase				)			->bool:






		"""simple docstring"""


		if not tree:
				return True
		if tree.left and tree.right:
				return is_full_binary_tree(tree.left				) and is_full_binary_tree(tree.right				)
		else:
				return not tree.left and not tree.right

def 						snake_case__       (					)			->None:  # Main function for testing.






		"""simple docstring"""


		__lowercase				:		str												=				Node(1				)
		__lowercase				:		int												=				Node(2				)
		__lowercase				:		Optional[int]												=				Node(3				)
		__lowercase				:		int												=				Node(4				)
		__lowercase				:		Dict												=				Node(5				)
		__lowercase				:		int												=				Node(6				)
		__lowercase				:		Tuple												=				Node(7				)
		__lowercase				:		Optional[Any]												=				Node(8				)
		__lowercase				:		Optional[int]												=				Node(9				)

		print(is_full_binary_tree(_lowerCamelCase				)				)
		print(depth_of_tree(_lowerCamelCase				)				)
		print("Tree is: "				)
		display(_lowerCamelCase				)


if __name__ == "__main__":
						main()






"""simple docstring"""







def 						snake_case__       (					_lowerCamelCase				)			->list:






		"""simple docstring"""


		__lowercase				:		Optional[int]												=				[0] * len(_lowerCamelCase				)

		for i in range(1,  len(_lowerCamelCase				)				):
				# use last results for better performance - dynamic programming
				__lowercase				:		Optional[Any]												=				prefix_result[i - 1]
				while j > 0 and input_string[i] != input_string[j]:
						__lowercase				:		List[str]												=				prefix_result[j - 1]

				if input_string[i] == input_string[j]:
						j += 1
				__lowercase				:		Any												=				j

		return prefix_result

def 						snake_case__       (					_lowerCamelCase				)			->int:






		"""simple docstring"""


		return max(prefix_function(_lowerCamelCase				)				)


if __name__ == "__main__":
						import doctest

						doctest.testmod()
