Binary trees

"""
- Create the TreeNode class.
- height()
- size()
- count_leaves()
- preorder_traversal()
- inorder_traversal()
- postorder_traversal()
- level_order_traversal()
- mirror()
- is_complete_tree()
- find_lca()
- insert()
- delete()
"""
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# Height Calculation
def height(node):
    if node is None:
        return -1
    return max(height(node.left), height(node.right)) + 1

# Size Calculation
def size(node):
    if node is None:
        return 0
    return size(node.left) + size(node.right) + 1

# Counting the number of leaf nodes
def count_leaves(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return 1
    return count_leaves(node.left) + count_leaves(node.right)

# Traversals: Pre-order, In-order, Post-order, Level-order
def preorder_traversal(root):
    return [root.value] + preorder_traversal(root.left) + preorder_traversal(root.right) if root else []

def inorder_traversal(root):
    return inorder_traversal(root.left) + [root.value] + inorder_traversal(root.right) if root else []

def postorder_traversal(root):
    return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.value] if root else []

def level_order_traversal(root):
    if not root:
        return []
    result, queue = [], [root]
    while queue:
        node = queue.pop(0)
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

# Mirroring (inverting) the binary tree
def mirror(node):
    if node is None:
        return None
    node.left, node.right = node.right, node.left
    mirror(node.left)
    mirror(node.right)
    return node

# Checking if the binary tree is complete
def is_complete_tree(root):
    if not root:
        return True
    queue = [root]
    end = False
    while queue:
        current = queue.pop(0)
        if current:
            if end:
                return False
            queue.append(current.left)
            queue.append(current.right)
        else:
            end = True
    return True

def find_lca(root, n1, n2):
    """
    The lowest common ancestor is the deepest node that has both nodes as descendants.
    """
    # Base case
    if root is None:
        return None

    # If either n1 or n2 matches with root's value, report the presence by returning root
    if root.value == n1 or root.value == n2:
        return root

    # Look for keys in left and right subtrees
    left_lca = find_lca(root.left, n1, n2)
    right_lca = find_lca(root.right, n1, n2)

    # If both of the above calls return non-NULL, then one key is present in one subtree
    # and the other is present in the other, so this node is the LCA
    if left_lca and right_lca:
        return root

    # Otherwise check if left subtree or right subtree is LCA
    return left_lca if left_lca is not None else right_lca

# Insertion: Adds a node to the binary tree (level-order insertion for simplicity)
def insert(root, value):
    if root is None:
        return TreeNode(value)

    queue = [root]
    while queue:
        current = queue.pop(0)

        if current.left is None:
            current.left = TreeNode(value)
            break
        else:
            queue.append(current.left)

        if current.right is None:
            current.right = TreeNode(value)
            break
        else:
            queue.append(current.right)

    return root

# Deletion: Removes a node from the binary tree (simple level-order approach)
def delete(root, value):
    if root is None:
        return None

    if root.left is None and root.right is None:
        if root.value == value:
            return None
        else:
            return root

    key_node = None
    queue = [root]
    temp = None
    while queue:
        temp = queue.pop(0)
        if temp.value == value:
            key_node = temp

        if temp.left:
            queue.append(temp.left)
        if temp.right:
            queue.append(temp.right)

    if key_node:
        x = temp.value
        _delete_deepest(root, temp)
        key_node.value = x

    return root

def _delete_deepest(root, del_node):
    queue = [root]
    while queue:
        temp = queue.pop(0)
        if temp is del_node:
            temp = None
            return
        if temp.right:
            if temp.right is del_node:
                temp.right = None
                return
            else:
                queue.append(temp.right)
        if temp.left:
            if temp.left is del_node:
                temp.left = None
                return
            else:
                queue.append(temp.left)

# Example usage
root = TreeNode(1)
root = insert(root, 2)
root = insert(root, 3)
root = insert(root, 4)
root = insert(root, 5)

# Example usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Size of the tree:", size(root))
print("Height of the tree:", height(root))
print("Number of leaf nodes:", count_leaves(root))  # Output: 3
print("Is the tree complete?", is_complete_tree(root))  # Output: True

print("Pre-order traversal:", preorder_traversal(root))
print("In-order traversal:", inorder_traversal(root))
print("Post-order traversal:", postorder_traversal(root))
print("Level-order traversal:", level_order_traversal(root))

root = mirror(root)
print("Level-order traversal after mirroring:", level_order_traversal(root))  # Output: [1, 3, 2, 5, 4]

root = insert(root, 8)
print("Level-order traversal after inserting 8:", level_order_traversal(root))

root = delete(root, 3)
print("Level-order traversal after deleting 3:", level_order_traversal(root))

print("Lowest common ancestor of 5 and 4:", find_lca(root, 5, 4).value)