Binary Tree

A tree is a hierarchical data structure made of nodes. Every node can point to child nodes, and the top node is called the Head (or Root).

Tree vs Binary Tree

A general tree node can have any number of children:

        [Root]
       /   |   \
     [A]  [B]  [C]

A binary tree restricts each node to at most two children: a left node and a right node.

class Node:
    value: int
    left: Node   # left child
    right: Node  # right child

       [Root]
      /      \
   [left]  [right]

Terminology

Root — the top node (the head of the tree)
Leaf — a node with no children
Height — the number of levels from root to the deepest leaf
Subtree — any node and all its descendants

         [10]         ← root (level 0)
        /    \
      [5]    [15]     ← level 1
     /   \
   [3]   [7]          ← level 2, leaves

Binary Search Tree (BST)

The most common type of binary tree. It has one rule:

Left child < Parent < Right child

This ordering makes searching extremely efficient.

         [10]
        /    \
      [5]    [15]
     /   \      \
   [3]   [7]   [20]

To find 7: start at 10 → go left (7 < 10) → reach 5 → go right (7 > 5) → found 7. Only 3 steps for a 6-node tree.

Big O for BST

Operation	Average	Worst (unbalanced)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

O(log n) because at each node you eliminate half the remaining nodes by going left or right.

Worst case O(n) happens when the tree becomes a straight line (all elements inserted in order), behaving like a linked list.

B-Tree

A B-Tree generalizes the binary tree by allowing each node to have more than 2 children. It is widely used in databases and file systems (e.g., PostgreSQL indexes, ext4).

          [Root]
         /   |   \
       [A]  [B]  [C]

The advantage: fewer levels means fewer reads — critical when data lives on disk and each level costs a disk I/O.

Heap

A Heap is a binary tree with one extra rule about ordering.

Min-Heap: the root is always the smallest value. Every parent is smaller than its children.

         [10]          ← always the minimum
        /    \
      [20]   [11]
     /    \
   [20]  [30]

Max-Heap: the root is always the largest value.

Heaps are used to implement priority queues — always get the min/max in O(1), insert in O(log n).

Big O for Heap

Operation	Time
Get min/max	O(1)
Insert	O(log n)
Remove min/max	O(log n)

Tree Traversals

Three ways to visit every node in a binary tree:

In-order (left → root → right) — gives sorted output for a BST:

3 → 5 → 7 → 10 → 15 → 20

Pre-order (root → left → right) — useful for copying a tree:

10 → 5 → 3 → 7 → 15 → 20

Post-order (left → right → root) — useful for deleting a tree:

3 → 7 → 5 → 20 → 15 → 10

In Python

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)

Python's heapq module provides a min-heap:

import heapq

heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
heapq.heappush(heap, 11)

heapq.heappop(heap)  # → 10 (always the minimum)

Key Takeaways

A tree is hierarchical: one root, nodes with children, leaves at the bottom.
A binary tree limits each node to at most 2 children (left and right).
A BST keeps left < parent < right, enabling O(log n) search.
A B-Tree allows more than 2 children per node — used in databases for efficient disk reads.
A Heap is a binary tree where the root is always the min (or max) — perfect for priority queues.