Trees & Hierarchies

binary tree

A binary tree is the most common and most useful shape of tree: every node has at most two children, conventionally called the left child and the right child. That tidy two-way branching is enough to express an enormous range of ideas, and because each node only ever holds two pointers it is cheap to store and easy to reason about.

The 'left' and 'right' labels are not interchangeable — they carry meaning. In a binary search tree the left subtree holds smaller keys and the right holds larger ones; in an expression tree they separate the two operands of an operator. Many algorithms are naturally recursive on a binary tree: to do something to the whole tree, you do it to the left child, do it to the right child, and combine — a pattern you will see again and again.

A binary tree with n nodes can be as short as about log2(n) levels when it is full and balanced, or as tall as n levels when every node has a single child and it degenerates into a glorified linked list. The shape decides the cost: most operations take time proportional to the height, so keeping a binary tree short is the whole game, which is exactly what balanced trees and heaps are built to do.

int countNodes(Node* root) {
  if (root == nullptr) return 0;     // empty subtree
  return 1                           // this node
       + countNodes(root->left)      // + left side
       + countNodes(root->right);    // + right side
}

Counting nodes recursively — the shape of nearly every binary-tree algorithm.

"Binary" here means two-way branching, not the base-2 number system — in Chinese the tree sense is 二叉 (zh) / 二元 (zhHant).

Also called

二叉树二元樹