3
$\begingroup$

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.

$\endgroup$

migrated from stats.stackexchange.com Apr 7 '14 at 16:58

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

  • 1
    $\begingroup$ What's wrong with "$n$-th ancestor"? $\endgroup$ – Raphael Apr 7 '14 at 23:34
  • $\begingroup$ I must say I'm puzzled by the move of this post from stats to comp-sci. I thought of it as a diagram and the language used to refer to the illustration. $\endgroup$ – xtian Apr 9 '14 at 22:11
  • $\begingroup$ I don't understand your second sentence at all. As for the reasons for migration, you have to ask that of the Cross Validated guys (in their chat?); all I know is that this is firmly a computer science question so this is definitel a (the?) correct place for it. $\endgroup$ – Raphael Apr 9 '14 at 22:20
  • $\begingroup$ Ralph. "firmly a computer science question". Hate to burst your bubble, but graph theory predates computers. "The paper written by Leonhard Euler on the Seven Bridges of Königsberg and published in 1736 is regarded as the first paper in the history of graph theory." Wikipedia $\endgroup$ – xtian Apr 16 '14 at 15:26
0
$\begingroup$

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 $n$th 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.

$\endgroup$
  • $\begingroup$ Sounds good. Check $\endgroup$ – xtian Apr 9 '14 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.