class TreeNode: """Node of binary tree""" def __init__(self, value: int): self.value = value self.left = None self.right = None def is_leaf(self) -> bool: return self.left is None and self.right is None class BinarySearchTree: def __init__(self): self.root = None def insert(self, value: int): """ Insert value to the binary search tree. Args value (int): Value to insert """ if self.root is None: self.root = TreeNode(value) else: self._insert_recursive(self.root, value) def _insert_recursive(self, node, value): """Helper function for insert.""" if value < node.value: if node.left is None: node.left = TreeNode(value) else: self._insert_recursive(node.left, value) else: if node.right is None: node.right = TreeNode(value) else: self._insert_recursive(node.right, value) def load_from_file(self, filepath: str): """ Insert values in the file (row by row). The file should contain one value at each row. """ with open(filepath, 'r') as file: for line in file: self.insert(int(line.strip())) def print_tree(self): """ Nicely print tree to standard output. """ self._print_tree_recursive(self.root, 0) def _print_tree_recursive(self, node: TreeNode, level: int): """ Helper function for print_tree. Args node (TreeNode): The root of subtree to print. level (int): Level of the node in original tree. """ if node is not None: self._print_tree_recursive(node.right, level + 1) print(' ' * 4 * level + '->', node.value) self._print_tree_recursive(node.left, level + 1) def contains(self, value: int) -> int: """ Compute number of occurences of value in the tree. Args value (int): The value to look for. Returns int: Number of occurences. """ # NOTE is the function named appropriately ??? return self._contains_recursive(self.root, value) def _contains_recursive(self, node, value): if node is None: return 0 if node.value == value: return 1 + self._contains_recursive(node.left, value) + self._contains_recursive(node.right, value) elif value < node.value: return self._contains_recursive(node.left, value) else: return self._contains_recursive(node.right, value) def find_min(self) -> int: """ Find minimum value in the tree. Returns int: Minimum value. """ current = self.root while current.left is not None: current = current.left return current.value def find_max(self): # NOTE: this implementation works only in Search Trees (where values are ordered) current = self.root while current.right is not None: current = current.right return current.value def calculate_average(self): total_sum, total_count = self._calculate_sum_and_count(self.root) return total_sum / total_count if total_count > 0 else 0 def _calculate_sum_and_count(self, node): if node is None: return (0, 0) left_sum, left_count = self._calculate_sum_and_count(node.left) right_sum, right_count = self._calculate_sum_and_count(node.right) return (node.value + left_sum + right_sum, 1 + left_count + right_count) def sum(self): return self._sum_recursive(self.root) def _sum_recursive(self, node): if node is None: return 0 return self._sum_recursive(node.left) + node.value + self._sum_recursive(node.right) def leaves_count(self): return self._leaves_count_recursive(self.root) def _leaves_count_recursive(self, node): if node is None: return 0 if node.left is None and node.right is None: # TODO: DRY -> create and use node.is_leaf() instead # node is leaf return 1 # node is not leaf return self._leaves_count_recursive(node.left) + self._leaves_count_recursive(node.right) def height(self): return self._height_recursive(self.root) def _height_recursive(self, node): if node is None: return 0 return 1 + max(self._height_recursive(node.left), self._height_recursive(node.right)) def get_values_of_deepest_leaves(self): max_depth = 0 values_at_max_depth = [] def search(node, depth): nonlocal max_depth nonlocal values_at_max_depth if node is None: # alternative solution: call search(node.left,...) only if node.left exists return if node.is_leaf(): if depth > max_depth: max_depth = depth values_at_max_depth = [node.value] elif depth == max_depth: values_at_max_depth.append(node.value) else: search(node.left, depth+1) search(node.right, depth+1) search(self.root, 0) return values_at_max_depth def get_level_with_most_nodes(self): # Two possible approaches: # Option 1: DFS (as in previous), in each node update "global" list that maps level-->#nodes # Option 2: BFS (level by level), and just compute maximum during that # Lets try option 2: if self.root is None: return None most_occupied_level, nodes_at_most_occ_level = 0, 1 current_level = [self.root] current_level_depth = 0 while current_level: # while not empty next_level = [] for node in current_level: if node.left is not None: next_level.append(node.left) if node.right is not None: next_level.append(node.right) # probably better solution: # for child in node.children(): # if child is not None: # next_level.append(child) current_level = next_level current_level_depth += 1 if len(current_level) > nodes_at_most_occ_level: most_occupied_level = current_level_depth nodes_at_most_occ_level = len(current_level) return most_occupied_level def is_symmetric(self) -> bool: def _check_symmetry(left_node, right_node): if left_node is None and right_node is None: return True if left_node is not None and right_node is not None: return ( _check_symmetry(left_node.left, right_node.right) and _check_symmetry(left_node.right, right_node.left) ) return False return _check_symmetry(self.root.left, self.root.right) # Příklad použití: tree = BinarySearchTree() tree.load_from_file('08/tree_data.txt') tree.print_tree() print("number of occurences of value 5", tree.contains(5)) # print(tree.find_min()) # print(tree.find_max()) # print(tree.calculate_average()) print("sum", tree.sum()) print("height", tree.height()) print("leaves count", tree.leaves_count()) print("values of deepest leaves", tree.get_values_of_deepest_leaves()) print("most occupied level", tree.get_level_with_most_nodes())