Trees

Trees are hierarchical data structures. Unlike arrays and linked lists which are linear, trees branch into parent-child relationships. They are used everywhere: file systems, HTML DOM, database indexes, and network routing.

Tree Terminology

• Root: the topmost node with no parent
• Child: a node directly connected below another node
• Parent: a node directly connected above a child
• Leaf: a node with no children
• Depth: number of edges from the root to the node
• Height: number of edges on the longest path from the node to a leaf

Binary Trees

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

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

Tree Traversals

Preorder (Root → Left → Right)

def preorder(node):
    if node:
        print(node.val, end=" ")
        preorder(node.left)
        preorder(node.right)

Inorder (Left → Root → Right)

def inorder(node):
    if node:
        inorder(node.left)
        print(node.val, end=" ")
        inorder(node.right)

Postorder (Left → Right → Root)

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.val, end=" ")

Level-Order (BFS)

from collections import deque

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

Array Representation of Binary Tree

A binary tree can be stored in an array: index 0 holds the root, and for any node at index i, its left child is at 2i + 1 and right child at 2i + 2. This is the basis for heap data structures.

Binary Search Tree (BST)

A BST is a binary tree where for every node: all values in the left subtree are smaller, and all values in the right subtree are larger.

Insert

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

Search

def search(root, target):
    if root is None or root.val == target:
        return root
    if target < root.val:
        return search(root.left, target)
    return search(root.right, target)

Delete

def delete(root, val):
    if root is None:
        return None
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        # Node with two children: find inorder successor
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root

AVL Trees (Balanced BST)

AVL trees maintain balance using a balance factor (height of left - height of right). When a node becomes unbalanced (factor ±2), one of four rotations restores balance: left, right, left-right, or right-left rotation.

Heap (Binary Heap)

A heap is a complete binary tree that satisfies the heap property:

• Max-heap: each parent is greater than or equal to its children
• Min-heap: each parent is less than or equal to its children

Heapify (Building a heap from an array)

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def build_max_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)