Subträd

Subträd is the Swedish term for subtree, a fundamental concept in rooted trees. The subtree rooted at a node v in a rooted tree T = (V, E) consists of v and every node reachable from v by following child links, together with the edges on those paths. The size of a subtree is the number of nodes it contains, and its height is the maximum distance from v to a leaf within that subtree. A proper subtree of v is any subtree rooted at a descendant of v, excluding v itself.

In practice, trees are stored as rooted structures with parent-child relationships, typically using adjacency lists. Subtree queries are common, such as summing values stored at nodes or applying updates to all nodes in a subtree. A standard technique uses an Euler tour or DFS order to map each subtree to a contiguous range in an array, enabling fast range queries and updates with data structures like segment trees or Fenwick trees. Often tin[v] and tout[v] denote entry and exit times, so the nodes in the subtree of v correspond to the interval [tin[v], tout[v]].

Subtrees are central in tree dynamic programming, where computations for a node rely on its descendants, and in problems involving subtree isomorphism, which tests whether two subtrees have the same shape. In binary trees, the subtree rooted at a node includes that node and up to two children, left and right. The term subträd is widely used in Swedish literature to denote these ideas and their computational applications.