Binary Trees and Binary Search Trees

A tree is a hierarchical data structure made of nodes connected by edges. Unlike a linked list, where each node points to one next node, a binary tree node points to up to two children: a left child and a right child. This branching shape lets us search and organize data far faster than scanning a list.

Tree Vocabulary

• Root — the top node, the one with no parent
• Leaf — a node with no children
• Parent / Child — a node's direct connections up and down
• Subtree — any node together with all its descendants
• Height — the number of edges from the root to the deepest leaf

The BST Property

A binary search tree is a binary tree with one rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This rule is what makes BSTs useful — it lets us throw away half the tree at every step, just like binary search on a sorted array.

In a balanced BST, search, insert, and delete are all O(log n). In a degenerate BST that looks like a linked list (always inserting in sorted order), they're O(n). Self-balancing trees like AVL and red-black trees fix that.

The Three Traversals

Three classic ways to visit every node:

• Inorder (left, root, right) — visits a BST's values in sorted order
• Preorder (root, left, right) — useful for copying or serializing a tree
• Postorder (left, right, root) — useful for deleting or evaluating expressions

Insert and Search

Both follow the same recipe: compare the target to the current node, then recurse left or right depending on whether it's smaller or larger. Insert places a new node when it hits a null spot. Search returns true when it finds the value, false when it falls off the tree.

Try It Yourself

• Add a find_min function that walks left until there are no more left children
• Write a function to count the number of nodes in a tree
• Implement delete for a BST (it's surprisingly tricky — three cases to handle)