Lesson 6 of 9

Trees & Binary Search

A tree arranges nodes in a hierarchy with one root and no cycles. You'll learn how programs store things like folders, the and indexes, and how search works.

Tree vocabulary: 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 ().


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 track).


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

# Note: in_order() on a BST prints values in sorted order.

Same halving idea works on a plain sorted — 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 is easy to get slightly wrong with off-by-one , so learn this standard form.


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

Finished reading?Mark it done to track your progress.

Tip: use the ← and → keys to move between lessons.