Tree (abstract data type)

In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes.

These constraints mean there are no cycles or "loops" (no node can be its own ancestor), and also that each child can be treated like the root node of its own subtree, making recursion a useful technique for tree traversal.

Binary trees are a commonly used type, which constrain the number of children for each parent to at most two.

Representations might also be more complicated, for example using indexes or ancestor lists for performance.

Typically siblings have an order, with the first one conventionally drawn on the left.

Some definitions allow a tree to have no nodes at all, in which case it is called empty.

In working memory, nodes are typically dynamically allocated records with pointers to their children, their parents, or both, as well as any associated data.

In relational databases, nodes are typically represented as table rows, with indexed row IDs facilitating pointers between parents and children.

Concretely, it is (if required to be non-empty): Often trees have a fixed (more properly, bounded) branching factor (outdegree), particularly always having two child nodes (possibly empty, hence at most two non-empty child nodes), hence a "binary tree".