Trees and Binary Search Trees

After this lesson, you will be able to: Implement a binary search tree with insert, search, and delete, perform all four traversals, and understand why balancing matters.

Trees organize data hierarchically. Binary search trees keep data sorted so search, insert, and delete are O(log n) when balanced. Trees underpin databases, file systems, and the way compilers represent code.

Prerequisites:Hash Tables

Trees and binary trees

A tree is a set of nodes where each node has children and exactly one parent (except the root, which has none). A binary tree restricts each node to at most two children, called left and right. Trees model hierarchy: a file system, an org chart, the DOM of a webpage, the parse tree of a program. The depth of a balanced binary tree with n nodes is about log n, which is the source of their speed.

A binary search tree (BST)

The BST rule: left subtree values are smaller, right subtree values are larger.

python

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return TreeNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node            # ignore duplicates

    def search(self, value):
        node = self.root
        while node:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False

Why search is O(log n)

Because of the BST rule, every comparison lets you discard half the remaining tree, exactly like binary search on a sorted array. In a balanced tree of n nodes, you make about log n comparisons to find anything. That is why a balanced BST can search a billion items in around 30 steps. The catch is in the word balanced.

The four traversals

Different orders of visiting nodes solve different problems.

python

# Inorder (left, node, right): visits a BST in SORTED order
def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.value)
        inorder(node.right, out)

# Preorder (node, left, right): used to COPY a tree or serialize it
# Postorder (left, right, node): used to DELETE a tree or evaluate expressions
# Level-order (BFS, ring by ring): uses a queue, not recursion
from collections import deque
def level_order(root):
    out, q = [], deque([root] if root else [])
    while q:
        node = q.popleft()
        out.append(node.value)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return out

Common mistakes only experienced devs catch

Assuming a BST is balanced when it is not (inserting sorted data is the classic trap that gives you O(n)). Forgetting that inorder traversal of a BST yields sorted output (a free, elegant sort and a common interview insight). Mishandling the delete case where a node has two children (replace with the inorder successor). Using recursion on a very deep, unbalanced tree and overflowing the call stack. Confusing a binary tree (any two children) with a binary search tree (ordered).

←Hash Tables

Back to Data Structures

Heaps→