# 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

# AST

The terms I've made up are general definitions of two kinds of tree data structure. I define them more precisely in later sections but in summary they are:

• A Sparse Tree aka AST. A sparse subset of a tree.

• Annotated Subset Tree aka AST. A sparse tree formed via "annotation".

Why define terms to distinguish the concepts when their acronyms eliminate the distinction? Because eliminating the distinction is the most important thing, even though defining the distinction is also important enough to warrant my question and this answer.

# AST typically refers to Abstract Syntax Tree

One existing typical meaning of AST in the CS world is the specific context I had in mind when I posed my question.2

So now we have not two but three ASTs. In the section Why three ASTs?!? below I'll return to why I'm defining three distinct tree concepts that all share the same acronym.

# A Sparse Tree

By A Sparse Tree3 I mean a node of a tree data structure that serves as a root, plus any "well formed"4 potentially sparse subset tree formed of branch and leaf nodes relative to that root.

My example will be A Sparse Tree formed from a parse tree.5

If source code is like this:

foo = bar # Assign bar to identifier foo


And the parse tree is like this:

TOP
statement                   foo = bar # Assign bar to identifier foo
assignment                foo = bar
identifier              foo
assignment operator     =
identifier              bar
end-of-line-comment       # Assign bar to identifier foo


then the following represents two of many possible sparse trees based on that single parse tree:

# A Sparse Tree:
assignment                foo = bar
identifier              foo
identifier              bar

# Another Sparse Tree:
end-of-line-comment       # Assign bar to identifier foo


# Annotated Subset Tree

By Annotated Subset Tree6 I mean A Sparse Tree represented/stored by annotating a subset of the nodes of a tree.

# Why three ASTs?!?

One abstract use case for sparse trees is forming an Abstract Syntax Tree that consists of annotations of the Parse Tree generated by a top down parser.

When the distinction between A Sparse Tree, an Annotated Subset Tree, and an Abstract Syntax Tree is moot -- which is most of the time -- just use the acronym AST without worrying about the ambiguity, because, by my definitions, it doesn't matter.7

That's why the terms I've coined share the same acronym: AST -- so they can be understood as theoretically distinct things but, for some parser implementations, the same thing in practice.

# Footnotes

1 My question was originally an attempt to find out if there was already an accepted term for what I described, generically in regard to trees, without regard for Abstract Syntax Trees. 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 By "well formed" I mean that each node in the sparse/subset tree contains content from, and/or pointers to, the content of other nodes, always in the direction of the tree's leaves.

5 The word "sparse" is onomatopoeically reminiscent of "parse". A "happy mnemonic accident" given that that the context for me naming these things is a sparse tree formed from a parse tree. It also reminds me of "A partridge in a pear tree" and I fantasise I will one day come up with and publish a worthy pun along those lines. :)

6 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.

7 Of course, the usual use of the term "AST" in a CS context is an Abstract Syntax Tree. The whole point of this SO was to pick abstract terms describing a concrete approach that may be taken by parsers storing an AST. That the terms all initialise to AST, with Abstract Syntax Tree being the dominant meaning of that acronym, is, of course, deliberate, and, imo, delightful.