# 1.Binary Tree Traversal
# Node of Binary Tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Inorder: Left -> Root -> Right
def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

# Preorder: Root -> Left -> Right
def preorder(root):
    if root:
        print(root.data, end=" ")
        preorder(root.left)
        preorder(root.right)

# Postorder: Left -> Right -> Root
def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.data, end=" ")

# Create Binary Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Display Traversals
print("Inorder Traversal:")
inorder(root)
print("\n\nPreorder Traversal:")
preorder(root)
print("\n\nPostorder Traversal:")
postorder(root)


# 2. Iterative traversal in binary tree(Inorder Traversal) 
# Node of Binary Tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Iterative Inorder Traversal
def inorder(root):
    stack = []
    current = root
    while stack or current:
        # Go to the leftmost node
        while current:
            stack.append(current)
            current = current.left
        # Visit the node
        current = stack.pop()
        print(current.data, end=" ")
        # Move to the right subtree
        current = current.right

# Create Binary Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Display Traversal
print("Iterative Inorder Traversal:")
inorder(root)



# 3. Counting Nodes — Total, Leaf and Internal 
# Node of Binary Tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Count Total Nodes
def count_nodes(root):
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

# Count Leaf Nodes
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)

# Count Internal Nodes
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)

# Create Binary Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)

# Display Results
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
# Node of Binary Tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Find Minimum Value
def find_min(root):
    if root is None:
        return float('inf')
    return min(
        root.data,
        find_min(root.left),
        find_min(root.right)
    )

# Find Maximum Value
def find_max(root):
    if root is None:
        return float('-inf')
    return max(
        root.data,
        find_max(root.left),
        find_max(root.right)
    )

# Create Binary Tree
root = Node(10)
root.left = Node(5)
root.right = Node(20)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.right = Node(25)

# Display Results
print("Minimum Value:", find_min(root))
print("Maximum Value:", find_max(root))



# 5. Binary Search Tree — Insertion and Searching
# Node of Binary Search Tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Insert Element into BST
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

# Search Element in BST
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)

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

# Search for an Element
key = 40
if search(root, key):
    print(key, "found in BST")
else:
    print(key, "not found in BST")




