🌳 Trees & BSTs

Branching data structures

← Back to Algorithms

🌲 What is a tree?

A tree is a structure that branches out, like a family tree or a folder structure. It starts at the root and each node can have children. Nodes with no children are leaves.

(8) <- root / \ (3) (10) / \ \ (1) (6) (14) <- leaves

Trees are everywhere: file systems, the HTML on this page (the DOM!), decision trees in AI, and database indexes.

🌴 Binary trees

A binary tree is a tree where each node has at most two children: a left and a right. We build it with a node class:

class Node: def __init__(self, value): self.value = value self.left = None self.right = None root = Node(8) root.left = Node(3) root.right = Node(10)

🔎 Binary Search Tree (BST)

A BST follows one golden rule at every node: smaller values go left, larger values go right. This keeps the data organized so you can search it in O(log n) — just like binary search!

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

🚶 Traversals — visiting every node

Because trees branch, we use recursion to visit nodes. In-order traversal of a BST magically returns the values in sorted order!

def in_order(root): if root is None: return in_order(root.left) # 1. left subtree print(root.value) # 2. this node in_order(root.right) # 3. right subtree

💡 Three traversal orders

  • In-order (left, node, right) → sorted output for a BST.
  • Pre-order (node, left, right) → copy/serialize a tree.
  • Post-order (left, right, node) → delete a tree safely.

✅ What you learned

  • A tree branches from a root; nodes have children, leaves have none.
  • A binary tree node has left and right children.
  • A BST keeps smaller left, larger right → fast O(log n) search.
  • In-order traversal of a BST prints values in sorted order.