Trees: Holding Data in Branches
The structure that mirrors hierarchy — O(log n) binary search trees, why in-order traversal yields sorted output, and how C, Java, C#, and Python hold trees
What a tree is: hierarchy as-is
Arrays, linked lists, stacks, and queues all hold data in a single line. A tree introduces branching: from a single root, edges reach down to nodes, each node may have children, and a node with no children is a leaf.
50 <- the root / \ 30 70 <- nodes / \ / \ 20 40 60 80 <- nodes without children are leaves Branches grow downward (trees are drawn upside down)
Folders and files, the elements of an HTML page (the DOM), organization charts — the nesting and hierarchy all around us map onto trees directly. Not having to flatten hierarchy into a line is the first reason to use a tree.
Binary search trees: smaller to the left, larger to the right
Add one rule to a tree and it becomes a powerful search tool. A binary search tree (BST) keeps this promise at every node: everything in the left subtree is smaller, everything in the right subtree is larger.
Searching for 60: compare and descend left or right 50 60 > 50 -> go right / \ 30 70 60 < 70 -> go left / \ / \ 20 40 [60] 80 <- found in 3 comparisons Every comparison halves the candidates -> O(log n) if balanced (about 20 steps even for a million)
To find something, start at the root and repeatedly compare, going left or right. Each comparison halves the candidates, so the number of comparisons is "how many times n can be halved down to 1" — written log n. If the tree is balanced, the search takes O(log n): about 20 comparisons even for a million entries.
Recall the Arrays and Lists page: arrays access by index quickly but insert in the middle in O(n), while linked lists insert by re-pointing but take O(n) to reach the right spot. The binary search tree aims for the best of both: O(log n) search and O(log n) insertion.
Beware of lopsided trees
Insert already-sorted values one by one and the tree grows into a straight line — effectively a linked list, degrading search to O(n). Practical trees rebalance themselves on every insertion or deletion — these are self-balancing trees (AVL trees, red-black trees). Java's TreeMap uses one of them — a red-black tree — inside.
Traversal: reading a tree as a line
Visiting every element of a tree is called traversal. Three orders are classic — pre-order (yourself first), in-order (left → yourself → right), and post-order (children first) — plus level order, which reads shallow levels first. These four are all you need to remember.
In-order traversal: left child -> yourself -> right child 50 / \ 30 70 / \ / \ 20 40 60 80 Values come out as: 20, 30, 40, 50, 60, 70, 80 -> reading a BST in-order yields a sorted sequence
In-order traversal has a delightful property: reading a binary search tree in-order produces the values in sorted order. And note the implementations — level order uses a queue, and depth-first orders use a stack (or recursion). The structures from the previous two pages return as the tools for walking trees.
Where trees are used
Hierarchical data is almost always a tree: file systems, the DOM a browser holds for a page, and the syntax trees a compiler builds to understand a program.
Trees also sit at the heart of search. The B-tree used in database indexes is a many-branched cousin of the binary search tree, and the heap inside a priority queue is a kind of tree as well.
Across languages: C, Java, C#, and Python
In C
/* C: no standard tree — build nodes from a struct and pointers */ struct Node { int key; struct Node *left; /* left child (smaller keys) */ struct Node *right; /* right child (larger keys) */ };
C has no standard tree. You build the nodes from a struct and pointers — a linked list whose single "next" has become two: "left" and "right".
In Java
// A Map whose keys stay in sorted order (a red-black tree inside) TreeMap<Integer, String> map = new TreeMap<>(); map.put(50, "root"); map.put(30, "left"); map.put(70, "right"); map.firstKey(); // 30 — the smallest key map.ceilingKey(60); // 70 — "smallest key >= 60", also O(log n)
When you need keys kept in sorted order with search, insertion, and deletion all in O(log n), Java offers TreeMap / TreeSet. Inside is a red-black tree — a self-balancing binary search tree that restores its shape after every insertion and deletion using "color" rules.
// Inside TreeMap (simplified from OpenJDK) static final class Entry<K,V> { K key; V value; Entry<K,V> left; // left child (smaller keys) Entry<K,V> right; // right child (larger keys) Entry<K,V> parent; // parent boolean color; // red or black — the balancing information }
Choosing between TreeMap and HashMap comes down to this: if you need no ordering and want the fastest single get/put, use HashMap (a map that computes each key's storage slot directly from the key — average O(1)). If you want to iterate keys in sorted order or ask range questions like "the smallest key that is at least 60", use TreeMap (O(log n)).
In C#
// C#: SortedDictionary<K,V> (a red-black tree inside) var map = new SortedDictionary<int, string>(); map[50] = "root"; map[30] = "left"; map[70] = "right"; // keys always enumerate in sorted order: 30, 50, 70
C#'s SortedDictionary<K,V> is also a red-black tree inside, and its keys always enumerate in sorted order (the similarly named SortedList is array-based and behaves differently).
In Python
# Python: the standard library has no balanced binary search tree # (dict is a hash table — average O(1), not kept in sorted order) data = {50: "root", 30: "left", 70: "right"} for key in sorted(data): # sort on demand when order matters print(key, data[key]) # for real needs, use an external library such as sortedcontainers
Python's standard library has no balanced binary search tree. dict is a hash table — average O(1), but keys are not kept in sorted order (insertion order is preserved, which is not the same thing). When sorted order matters, the practical options are sorting on demand with sorted() or an external library such as sortedcontainers.
Summary
A tree represents hierarchy directly: branches from a root, and nodes without children are leaves.
A binary search tree follows "smaller left, larger right": balanced, both search and insertion are O(log n); lopsided, it degrades to O(n) — hence self-balancing trees in practice.
In-order traversal yields sorted output. Level order walks with a queue, depth-first with a stack — data structures work in combination.
Java's TreeMap and C#'s SortedDictionary are red-black trees inside. Python has no standard balanced tree (dict is a hash table), and in C you build one from a struct and pointers.