Leaf node

related topics
{math, number, function}
{food, make, wine}
{specie, animal, plant}

In computer science, a leaf node or external node is a node of a tree data structure that has zero child nodes. Often, leaf nodes are the nodes farthest from the root node. In the graph theory tree, a leaf node is a vertex of degree 1 other than the root (except when the tree has only one vertex; then the root, too, is a leaf). Every tree has at least one leaf.

A non-leaf node is called an internal node. Some trees only store data in internal nodes, though this affects the dynamics of storing data in the tree. For example, with empty leaves, one can store an empty tree with a single leaf node. However with leaves that can store data, it is impossible to store an empty tree unless one stores some kind of marker data in the leaf that signifies that the leaf is to be empty (and thus the tree to be empty as well).

Conversely, some trees only store data in the leaf nodes, and use the internal nodes to hold other metadata, such as the range of values in the subtree rooted at that node. This type of tree is useful for range queries.

Another example of this is a parse tree. In this type of structure, the root node represents the starting symbol of a grammar, and all internal nodes represent derivations of non-terminals, which continue downward until concrete symbols are established. The leafs are the actual lexical tokens of the sentence.[1]

See also


Full article ▸

related documents
Almost all
Power associativity
Probability axioms
Integer sequence
Church–Rosser theorem
Measurable function
Gauss–Legendre algorithm
Krull dimension
Equivalence class
Center (group theory)
Catalan's constant
Gabriel Lamé
Digital Signature Algorithm
Laurent polynomial
Timeline of programming languages
Mary (programming language)
Sieve of Eratosthenes
Ring homomorphism
Two-out-of-five code
HTML scripting
Endomorphism ring
Doubling the cube
Euclidean distance
Arithmetic-geometric mean