Trees

In computer science, a Tree is a very popular abstract data type (ADT) or a data structure implementing this ADT that simulates a hierarchical Tree structure with a root value and subtrees of the children with a parent node, represented as a set of linked nodes.

A Tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the children) with the constraints that no reference is duplicated and none point to the root.

Alternatively, a Tree can be defined abstractly as a whole (globally) as an ordered Tree, with a value assigned to each node. Both these perspectives are useful: while a Tree can be analyzed mathematically as a whole, when actually represented as a data structure, it is usually represented and worked separately by a node (rather than as a list of nodes and an adjacency list of edges between nodes, as one may represent a digraph...