Binary Trees and Binary Search Trees

Trees organize data hierarchically: file systems, HTML documents, organization charts, and database indexes are all trees. The binary search tree (BST) adds one ordering rule to a binary tree and suddenly supports search, insert, and delete in O(log n). Everything you learned about recursion pays off here, because trees are recursive objects: every subtree is itself a tree.

What You'll Learn

• Tree vocabulary: root, leaf, height, subtree
• Building a binary tree from Node objects
• The three depth-first traversals, and why in-order visits a BST in sorted order
• BST insert and search in O(log n)

Trees Are Recursive Structures

A binary tree node has a value and up to two children. The same Node idea as linked lists, with left and right instead of next:

Both functions follow the same recursive template: handle the empty tree (base case), recurse into both children, combine. Nearly every tree algorithm looks like this.

The Three Depth-First Traversals

Traversal order is just "when do you visit the node relative to its children":

• Pre-order: node, left, right (copying or serializing a tree)
• In-order: left, node, right (sorted output on a BST)
• Post-order: left, right, node (deleting or sizing a tree bottom-up)

Look at the in-order output: [1, 3, 6, 8, 10, 14], perfectly sorted. That is not a coincidence; the tree above is a BST.

Binary Search Trees

The BST rule: for every node, everything in the left subtree is smaller, everything in the right subtree is larger. Searching then works exactly like binary search: compare and go left or right, discarding half the tree (on average) at each step. Open this one fullscreen and experiment:

The search path for 65 touches only 4 of the 8 nodes. On a balanced tree of a million nodes, that path is about 20 nodes long: O(log n).

The Balance Caveat

Insert already-sorted values into a BST and every node goes right: the "tree" degenerates into a linked list, and operations become O(n). Production systems use self-balancing trees (AVL, red-black) that rotate nodes to stay O(log n); Python's dict avoids the issue entirely by hashing. For interviews, know that the O(log n) claim assumes balance.

Where Trees Meet Real Life

• Your file system is a tree; sizes are computed post-order
• HTML is a tree; renderers walk it pre-order
• Databases index columns with B-trees, a generalization of BSTs
• Autocomplete uses tries, trees keyed by characters

Exercises

Key Takeaways

• Trees are recursive: most algorithms are base case + recurse both sides + combine
• Pre/in/post-order differ only in when the node is visited relative to its children
• In-order traversal of a BST produces sorted values
• BST search and insert are O(log n) when balanced, O(n) when degenerate
• Real systems keep trees balanced (AVL, red-black, B-trees) to protect the O(log n)