DSData Structures & Algorithms · Lesson 6 of 9

Trees & Binary Search

A tree is nodes and pointers arranged as a hierarchy: one root, branching children, no cycles. File systems, the DOM, JSON, org charts, database indexes — hierarchies are everywhere, and trees are how programs hold them.

Tree vocabulary in one breath: the root is the top node; children hang off parents; leaves have no children; height is the longest root-to-leaf path. A binary tree limits each node to two children, left and right. Since each subtree is itself a tree, tree code is naturally recursive — the base case is the empty tree (None).

Python

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

# Every tree question follows one recursive shape:
def height(node):
    if node is None:                # base case: empty tree
        return 0
    return 1 + max(height(node.left), height(node.right))

def count(node):
    if node is None:
        return 0
    return 1 + count(node.left) + count(node.right)

# Traversal — visit every node. "In-order" = left, self, right:
def in_order(node):
    if node is None:
        return
    in_order(node.left)
    print(node.value)
    in_order(node.right)

The star of the family is the binary search tree (BST): every node's left subtree holds smaller values, right subtree holds bigger ones. That single rule means search never explores both sides — compare, go left or right, half the tree eliminated per step. On a balanced tree that's O(log n): a million items found in ~20 comparisons. Databases index columns with tree variants (B-trees) for exactly this reason — it's why indexed queries are fast (see the SQL track).

Python

def search(node, target):
    if node is None:
        return False
    if target == node.value:
        return True
    if target < node.value:
        return search(node.left, target)     # skip entire right half
    return search(node.right, target)        # skip entire left half

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

# Bonus: in_order() on a BST prints values in sorted order. Free sort!

Same halving idea works on a plain sorted array — binary search, no tree needed. Check the middle; too small, discard the left half; too big, discard the right. O(log n) with three lines of state. It's the most implemented-slightly-wrong algorithm in history (off-by-one errors), so learn this canonical form.

Python

def binary_search(sorted_items, target):
    lo, hi = 0, len(sorted_items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_items[mid] == target:
            return mid
        if sorted_items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

binary_search([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23)   # 5
◆ Note
BSTs are only O(log n) while balanced. Insert already-sorted data into a naive BST and it degenerates into a linked list — O(n) again. Real implementations (red-black trees, AVL, B-trees) rebalance automatically; that's what your language's sorted containers and every database index use.