Fundamental Concepts and Terminology of Trees

Key Insight

A tree is formally defined as a finite set of one or more nodes, featuring a specially designated 'root' node. The remaining nodes are partitioned into zero or more disjoint sets, each of which is also a tree, called subtrees of the root. This recursive definition means a tree is defined in terms of smaller trees, avoiding circularity, and is inherently characteristic of tree structures in both computer algorithms and nature. Every node within a tree serves as the root of some subtree contained within the larger structure.

Key properties of nodes include 'degree,' which is the number of subtrees a node possesses; a node with degree zero is termed a 'terminal node' or 'leaf,' while others are 'branch nodes.' The 'level' of a node is defined recursively, with the root at level 0 and subsequent nodes at one higher level than their containing subtree's root. Trees can be 'ordered' if the relative sequence of subtrees matters, or 'oriented' if only their relative orientation, not specific order, is considered. Computer representations typically define an implicit ordering, making ordered trees of primary interest. A 'forest' is a set of zero or more disjoint trees, intrinsically linked to trees as deleting a root yields a forest, and adding a root to a forest forms a tree.

Descriptive terminology for trees, borrowed from family trees, includes 'parent' for a root of subtrees, 'children' for the roots of those subtrees, and 'siblings' for children sharing a parent. A node has at most one parent. 'Ancestor' and 'descendant' denote relationships spanning multiple levels, with 'inclusive ancestors' including the node itself, and 'proper ancestors' excluding it. While natural trees grow upwards, computational trees are almost universally drawn with the root at the top and leaves at the bottom, following the prevailing convention in computer literature (over 80 percent of cases), to establish a consistent visual and conceptual understanding for terms like 'top down' algorithms.