[mfoc]

For clarity, in (computer science) graph theory, a tree is a rooted, strict, connected, undirected, acyclic graph.

Explanation:

rooted: One vertex (also called a node) has been designated the root. The depth of a vertex is the number of branches in the path from root to the vertex. So depth of the root itself is zero and is the only vertex in the tree with this property.

strict: The edges have no weight(s).

connected: A graph is said to be connected if there is a path (edge) between every pair of vertices. From every node to any other node, there is a path to traverse.

undirected: The edges have no directionality specified.

acyclic: The are no closed loops (no cycles of any length).

graph: An abstract data structure consisting of a finite set of vertices and a finite set of edges (vertices pairs).

As another commenter has pointed out, the definition of a tree in mathematics is somewhat different...a tree need not have a root.

[foobarchu]

Out of curiosity does that definition come from somewhere specific? I would argue that strictness and undirectedness are not prerequisites for a data structure to be called a tree.

For example, B-trees are directed trees, and Huffman Coding is based on a weighted tree structure.

[mfoc]

I gave my good faith understanding of what a tree is, but your comment made me think more about it, and to look it up.

From chapter two of the book "Algorithmic Graph Theory and Sage" [1]; it states the following concerning directedness:

"A directed tree is a digraph which would be a tree if the directions on the edges were ignored." ... which is the correct definition from my understanding.

However, the authors go on to say:

"A rooted tree can be regarded as a directed tree since...Directed trees are pervasive in theoretical computer science, as they are useful structures for describing algorithms and relationships between objects in certain datasets."

So, colloquially (but perhaps not formally), one can refer to a directed, rooted, connected, acyclic graph as a tree.

Concerning weights, wolfram provides a definition of a strict graph [2] which specifies the unweighted qualifier (and undirected qualifier):

"A simple graph, also called a strict graph (Tutte 1998, p. 2), is an unweighted, undirected graph..."

The wolfram definition of a tree [3] includes the 'simple' qualifier:

Tree "is a simple, undirected, connected, acyclic graph..."

So, I would suggest formally, a tree cannot have weights (recall that weights are basically labels assigned to the edges).

Incidentally, I took down from the shelf my copy of The Art of Computer Programming (TAOCP) Volume One, and section 2.3 deals with trees exclusively. Donal Knuth asserts that trees are 'the most important nonlinear structures that arise in computer algorithms'. I skimmed the entire section and although he makes reference to weighted path lengths, I did not see any mention of weighted trees.

So, to my understanding, the original definition I proposed is valid, but I am very open to correction.

Concerning spanning trees and Huffman Coding - the tree are constructed from weighted graphs (not that the trees are weighted themselves). However, I understand where you are coming from, where again colloquially (but perhaps not formally), people often refer to and construct weighted trees.

At the beginning of Section 2.3.4 in TAOCP, Knuth makes the following important point concerning graph theory:

"Unfortunately, there will probably never be a standard terminology in this field, and so the author has followed the usual practice of comtemporary books on graph theory, namely to use words that are similar but not identical to the terms used in any other books on graph theory...the nomenclature used here is also biased towards computer applications".

So, in summary, my definition of a tree is open to debate :)

I am grateful for your question because in seeking out the answer, it has deepened my understanding of what a tree is.

[1] Algorithmic Graph Theory and Sage" by David Joyner, Minh Van Nguyen, David Phillip; Version 0.8-r1991;

[2] https://mathworld.wolfram.com/SimpleGraph.html

[3] https://mathworld.wolfram.com/Tree.html