# 1. Binary Tree Traversal
# For n nodes and height h: O(n) time and O(h) space for the recursion stack.
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)


def preorder(root):
    if root:
        print(root.data, end=" ")
        preorder(root.left)
        preorder(root.right)


def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.data, end=" ")


root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right = Node(4), Node(5)
print("Inorder traversal:")
inorder(root)
print("\nPreorder traversal:")
preorder(root)
print("\nPostorder traversal:")
postorder(root)
print()


# 2. Iterative traversal in binary tree (Inorder Traversal)
# For n nodes and height h: O(n) time and O(h) space for the stack.
def inorder_iterative(root):
    stack = []
    current = root

    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        print(current.data, end=" ")
        current = current.right


root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right = Node(4), Node(5)
print("Iterative inorder traversal:")
inorder_iterative(root)
print()


# 3. Counting Nodes — Total, Leaf and Internal
# Each counting function: O(n) time and O(h) space for the recursion stack.
def count_nodes(root):
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)


def count_leaf_nodes(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)


def count_internal_nodes(root):
    if root is None or (root.left is None and root.right is None):
        return 0
    return 1 + count_internal_nodes(root.left) + count_internal_nodes(root.right)


root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right, root.right.right = Node(4), Node(5), Node(6)
print("Total nodes:", count_nodes(root))
print("Leaf nodes:", count_leaf_nodes(root))
print("Internal nodes:", count_internal_nodes(root))


# 4. Finding Minimum and Maximum Value in Binary Tree
# Each function: O(n) time and O(h) space for the recursion stack.
def find_min(root):
    if root is None:
        return float("inf")
    return min(root.data, find_min(root.left), find_min(root.right))


def find_max(root):
    if root is None:
        return float("-inf")
    return max(root.data, find_max(root.left), find_max(root.right))


root = Node(10)
root.left, root.right = Node(5), Node(20)
root.left.left, root.left.right, root.right.right = Node(3), Node(7), Node(25)
print("Minimum value:", find_min(root))
print("Maximum value:", find_max(root))


# 5. Binary Search Tree — Insertion and Searching
# Insertion/search: O(h) time and O(h) recursive space; worst case O(n), balanced case O(log n).
def insert(root, data):
    if root is None:
        return Node(data)
    if data < root.data:
        root.left = insert(root.left, data)
    elif data > root.data:
        root.right = insert(root.right, data)
    return root


def search(root, key):
    if root is None:
        return False
    if root.data == key:
        return True
    if key < root.data:
        return search(root.left, key)
    return search(root.right, key)


root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)

key = 40
print(key, "found in BST" if search(root, key) else "not found in BST")
