Binary trees and binary search trees
Tree terminology, recursive traversals, and how binary search trees keep data sorted for O(log n) lookups.
In a binary tree each node has up to two children. In a binary search tree (BST), everything in a node's left subtree is smaller than it and everything in its right subtree is larger, so a lookup walks down one path.
Traversals visit every node, usually recursively:
- in-order (left, node, right) visits a BST in sorted order
- pre-order (node first) and post-order (children first, useful for freeing)
- level order uses a queue to go row by row
An unbalanced BST can degrade into a list; std::map uses a self-balancing tree to guarantee O(log n).
Example
#include <iostream>
#include <memory>
struct Node {
int key;
std::unique_ptr<Node> left, right;
explicit Node(int k) : key(k) {}
};
void insert(std::unique_ptr<Node> &t, int key) {
if (!t) t = std::make_unique<Node>(key);
else if (key < t->key) insert(t->left, key);
else insert(t->right, key);
}
void in_order(const Node *t) {
if (!t) return;
in_order(t->left.get());
std::cout << t->key << " ";
in_order(t->right.get());
}
int main() {
std::unique_ptr<Node> root;
for (int k : {50, 30, 70, 20, 40}) insert(root, k);
in_order(root.get());
std::cout << "\n";
return 0;
}
Output:
20 30 40 50 70
Watch it run: Inserting into a binary search tree