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))
    
            
    

# 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())