# Is “sparse subtree” an appropriate term for what I describe in this question?

Given a tree, with some nodes annotated, such that the annotations form another tree, I'm thinking "sparse subtree" is an appropriate term for describing the latter tree as it relates to the original tree. But I'd like to check with y'all because I plan to use the term in writing for an audience that will include CS savvy folk.

If not, I think "tree formed by the annotated subset of the nodes of the tree" will work but am hoping one of y'all will suggest something snappier than that.

• I'm not sure there is a standard term. Feel free to make up your own. – Yuval Filmus Jul 29 '18 at 16:48
• Just relax and choose whatever name you want. – Yuval Filmus Jul 29 '18 at 17:20
• Just be sure to explain at least once in some detail what the term means. – Sagnik Jul 30 '18 at 5:53
• I can now just quote or point to this SO question via your comment as the detailed explanation. Job done. Thank you @sagnik and Yuval. :) – raiph Jul 30 '18 at 10:23

The application context is transformation of a tree data structure called a parse tree (aka "concrete syntax tree") as part of creating an interpreter, compiler, or transpiler.2

# Definition of "sparse tree"

A "sparse tree" refers to the root or top node of a tree data structure plus any subset of the rest of its nodes.3

The name "sparse tree" is deliberately close in English to "parse tree" and this will be the only example I illustrate below.

If source code is like this:

foo = bar # assign bar to foo


And the parse tree is like this:

TOP
statement
assignment
identifier
assignment operator
identifier
end-of-line-comment


then the following could both represent sparse trees based on that parse tree:

TOP
assignment
identifier
identifier

TOP
end-of-line-comment


# Definition of "annotated subset tree"

An "annotated subset tree" is a sparse tree formed by annotating a subset of the nodes of a parse tree such that each annotation contains content and/or pointers to the annotations of other nodes in the direction of the tree's leaves.4

One of the primary uses for forming an annotation-based sparse tree is to store the abstract syntax tree corresponding to the parse tree (aka "concrete syntax tree"). That's why I've coined a term that shares the same acronym AST.

When the distinction between sparse tree, annotation subset tree, and abstract syntax tree is moot, which is most of the time, just use the acronym AST.

# Footnotes

1 My question was originally an attempt to find out if there was already an accepted term for what I described. Then it became documentation of that attempt and the CS exchange community's response:

I'm not sure there is a standard term. Feel free to make up your own.

Just be sure to explain at least once in some detail what the term means.

2 I deliberately didn't state this context for my question because my original goal was to find out if there was a generic CS term about such trees.

3 A google for "sparse tree" suggests a few things, most notably a new christmas tree aesthetic and an aspect of a software feature (Emacs Org mode), as well as some genuinely CSish notions, but I didn't find any matching what I've described in this answer.

4 A google for "annotated subset tree" suggests a variety of CSish notions, but I didn't find any matching what I've described in this answer.