Reading the Wikipedia article for common terminology for tree (data structure) t
ID: 652270 • Letter: R
Question
Reading the Wikipedia article for common terminology for tree (data structure) there are several near references, but I don't read a formal declaration for how to refer to a specific generation of a tree's subtrees.
For example,
Definition
As a data type, a tree has a value and children, and the children are themselves trees; [...] Due to the use of references to trees in the linked tree data structure, trees are often discussed implicitly assuming that they are being represented by references to the root node, as this is often how they are actually implemented.
And also,
Terminology.
"The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. [...] The root node has depth zero..."
The former implies subtree n could be refered to as the nth decendant of root or the nth tree. Can I be sure subtree only refers to decendants and not other branches at the same distance from root?
The latter refers to the height counting from the root (0). Again, height sounds uncommon to me. As in, "Please refer to the nodes at height 4 to see..." Since a tree is commonly displayed from the root branching downward, I'm predisposed to bias against the term height versus my preferred notion of depth.
Explanation / Answer
Commonly used phrases include,
"vertex at height h",
"vertex at depth d",
"vertex at distance d from the root".
"Subtree n" doesn't make any sense, except as the nth element in some enumeration of subtrees.
By the way, I'd avoid using n for anything other than the number of vertices in the graph. That bit of notation is so standard in graph theory that it's confusing for the reader to have n mean anything else.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.