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$
4
  • 1
    $\begingroup$ What's wrong with "$n$-th ancestor"? $\endgroup$
    – Raphael
    Apr 7, 2014 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, 2014 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, 2014 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, 2014 at 15:26

1 Answer 1

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$
1
  • $\begingroup$ Sounds good. Check $\endgroup$
    – xtian
    Apr 9, 2014 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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