Tree basics and binary trees
Trees organise data hierarchically: file systems, organisation charts, web page structure, and family trees all branch from a single root. Trees are among the most important structures in computing.
Tree vocabulary
A tree is a set of nodes connected by edges with no cycles, where one node is the root. Every other node has exactly one parent. Nodes with no children are leaves; others are internal nodes. The depth of a node is the number of edges from the root; the height of a tree is the greatest depth of any node. A subtree is a node together with all its descendants.
Binary trees
In a binary tree, each node has at most two children, called left and right. A full binary tree has every node with zero or two children; a complete binary tree fills every level except possibly the last, which is filled from the left; a perfect binary tree fills every level completely. A perfect binary tree of height h has 2^(h+1) - 1 nodes.
Height and node count
A binary tree with n nodes has height at least about log2(n), achieved when it is balanced, and at most n - 1, when it degenerates into a chain like a linked list. Since many tree operations cost time proportional to height, keeping trees short is the central concern of tree design.
Representations
Trees are usually built from node objects holding a value and pointers to children. A complete binary tree can be stored compactly in an array: the node at index i has children at 2i + 1 and 2i + 2, and its parent at (i - 1) // 2, using zero-based indexing. General trees with many children can use a list of children or the left-child, right-sibling form.
Recursion on trees
Trees are naturally recursive: a binary tree is either empty or a node with a left subtree and a right subtree. Many algorithms follow this shape directly. The height is 1 + the larger of the subtrees' heights (with an empty tree having height -1); the size is 1 + size(left) + size(right). Each visits every node once: O(n).
Expression trees
Arithmetic expressions form trees: internal nodes are operators and leaves are operands. (3 + 4) x 2 has x at the root, with a + subtree on the left and 2 on the right. Evaluating the tree recursively, computing children before applying the operator, gives the value. Compilers build such syntax trees when parsing code.
Trees in practice
File systems are trees of directories. HTML documents form the DOM tree that browsers manipulate. Decision trees classify data in machine learning. Tries store words letter by letter for fast prefix search, powering autocomplete. Database indexes use B-trees. Version histories, organisation charts, and tournament brackets are trees too.
Worked example
A tree with root A; A's children are B and C; B's children are D and E; C has one child, F, as its right child. Leaves: D, E, F. Depth of E: 2. Height of the tree: 2. Size: 6. It is not full, because C has only one child, and not complete, because the empty slot where C's left child would go comes before F on the bottom level. Its height, 2, is close to log2(6), about 2.6, so it is well balanced.
Key takeaways
A tree has a root, parent-child edges, and no cycles; leaves have no children. Depth counts edges from the root; height is the maximum depth. Binary trees have at most two children; full, complete, and perfect trees are special cases, and a perfect tree of height h has 2^(h+1) - 1 nodes. Height ranges from about log2(n) to n - 1, and operations often cost O(height). Complete trees fit in arrays with children at 2i + 1 and 2i + 2. Recursive algorithms follow tree shape. Expression trees, the DOM, tries, and B-trees are trees in practice.
Flashcard
Topmost node of a tree
Check your understanding
In the zero-based array representation of a complete binary tree, where are the children of the node at index 4?