A tree is a graph in which there is exactly one path between any two nodes. It is often used as a hierarchical data structure.
In computer science, a tree is a graph in which there is exactly one path between any two nodes. Often, the nodes are treated as a hierarchical data structure, such that there is a root node, and each child node also acts as a "root" of its subtree. An algorithm that uses a tree as a data structure will often traverse the tree starting at the root using recursion, working in logarithmic time.
Special-purpose trees include:
- binary-search tree
- abstract syntax tree (for example, an xml document may be thought of as a tree)
For a connected graph, a spanning tree consists of the nodes of the graph and a subset of the edges such that there is only one path between any pair of nodes.