Trees in Python

A tree is a hierarchical data structure made of nodes connected by edges. Trees represent parent-child relationships and are used heavily in searching, parsing, databases, and hierarchical storage.

Key advantages:

Represent hierarchy naturally
Many problems become easier with recursion
Balanced trees provide fast operations: O(log n)

Introduction to Trees (Terminology)

Root: top-most node
Edge: connection between nodes
Parent: a node that has children
Child: node that comes from a parent
Leaf: node with no children
Sibling: nodes with same parent
Depth: distance from root to node (edges count)
Height: max distance from node to leaf
Subtree: any node + all its descendants

Binary Trees and Their Types

A binary tree is a tree where each node has at most two children: left and right.

Types of Binary Trees

Full: every node has 0 or 2 children
Complete: filled level by level (left to right)
Perfect: all internal nodes have 2 children and all leaves same level
Balanced: height stays about log(n)

Implementing Binary Trees in Python

Node Class

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Example Tree Construction

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

Tree shape:

Tree Traversal Methods

Traversal means visiting all nodes systematically.

In-order Traversal (Left, Root, Right)

Used in BST to get sorted order.

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

Pre-order Traversal (Root, Left, Right)

Used for copying tree, prefix expressions.

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

Post-order Traversal (Left, Right, Root)

Used for deleting/freeing tree, postfix expressions.

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

Level-order Traversal (BFS)

Visits nodes level by level using a queue.

from collections import deque

def level_order(root):
    if not root:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.data, end=" ")
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

Binary Search Tree (BST)

A BST is a binary tree with ordering:

Left subtree values < node value
Right subtree values > node value

This enables average O(log n) search/insert/delete (if balanced).

Insertion in BST (O(h))

def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.data:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

Searching in BST (O(h))

def search_bst(root, value):
    if root is None or root.data == value:
        return root
    if value < root.data:
        return search_bst(root.left, value)
    return search_bst(root.right, value)

Deletion in BST (O(h))

Deletion cases:

Leaf node → remove directly
One child → replace node with child
Two children → replace with inorder successor (min in right subtree)

def min_value_node(node):
    current = node
    while current.left:
        current = current.left
    return current

def delete(root, key):
    if not root:
        return root

    if key < root.data:
        root.left = delete(root.left, key)
    elif key > root.data:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left

        temp = min_value_node(root.right)
        root.data = temp.data
        root.right = delete(root.right, temp.data)

    return root

AVL Trees and Balancing (Introduction)

AVL trees keep BST height balanced using rotations so performance stays O(log n).

Common rotations

Left rotation
Right rotation
Left-right rotation
Right-left rotation

Why needed: A normal BST can become skewed (like a linked list) if inserted in sorted order.

Applications of Trees

File systems (folders/subfolders)
Databases (B-Trees/B+ Trees)
Autocomplete (Trie trees)
Parsing expressions (syntax trees)
Routing / decision making (decision trees)

Summary

Trees represent hierarchical data and power many efficient algorithms. Binary trees teach recursion and traversals. BSTs add ordering for faster search, and AVL trees maintain balance for consistent performance.