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.

  • $\begingroup$ I'm not sure there is a standard term. Feel free to make up your own. $\endgroup$ Jul 29 '18 at 16:48
  • 1
    $\begingroup$ Just relax and choose whatever name you want. $\endgroup$ Jul 29 '18 at 17:20
  • $\begingroup$ Just be sure to explain at least once in some detail what the term means. $\endgroup$
    – Sagnik
    Jul 30 '18 at 5:53

2021 update: "embedded subtree"

In a discussion elsewhere8, I just encountered a term of interest with its own Wikipedia page: induced subgraph. This was roughly the sort of term I was after when I asked my original question, though it doesn't nail it.

It led me to google for "induced subtree". That has 80 matches and looked more appropriate for what I was after. But it still wasn't right because it disallows ancestor-descendant pairings that aren't parent-child.

That led me to "embedded subtree" in this paper which notes:

[In contrast to "induced subtrees"] Embedded subtrees ... allow not only direct parent-child edges, but also ancestor-descendant edges.

So maybe that's the right term.

On the other hand it still doesn't cover what I'm calling "annotation" -- the key notion that the nodes in the "subtree" are paired up with a subset of nodes in the original tree but are not actually the same nodes.

So due to that technical aspect, and for aesthetic reasons, I currently feel my original answer, which follows, remains as acceptable as it ever was. ;)


This self answer defines the terms and acronyms I've made up to refer to what I asked about.1

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 the mental modelling utility of eliminating the distinction is what I wanted to emphasize first and foremost, while still defining the distinction to make it clear what's going on behind the scenes.

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:

  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.

By "annotating" I mean hanging an additional node of data off selected nodes.

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


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 along branches proceeding in the direction of the tree's leaves from the sparse/subset tree's root node.

5 The word "sparse" is onomatopoeically reminiscent of "parse". This is a "happy mnemonic accident" given 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 have fantasized that 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. The fact that the terms all initialize to AST, with Abstract Syntax Tree being the dominant meaning of that acronym, is, of course, deliberate, and, imo, delightful.

8 A reddit.com/r/ProgrammingLanguages discussion

  • $\begingroup$ I don't want to rain on your parade, but this seems like a lot of effort spent on discussing the definition of a pretty trivial concept. I think you should take Yuval Filmus's advice and "just relax", as what you choose to call it doesn't matter that much (although "subtree induced by the annotated vertices" does work and is immediately comprehensible to anyone who has some familiarity with graph theory) $\endgroup$
    – Tassle
    Jan 24 at 21:48
  • $\begingroup$ @Tassle Us Brits just love wet weather, don't we? :) The definition in Induced subgraph says "graph whose vertex set is [node subset] and whose edge set consists of all of the edges in [node superset] that have both endpoints in [node subset]". But the edges between annotated nodes often skip intermediate nodes in the parse tree (which is what I meant by "sparse"). So Wikipedia's definition of an induced subgraph/subtree contradicts what I seek. I like "embed AST in CST" but thought there'd be a CS term for it. And now there is: AST. :) $\endgroup$
    – raiph
    Jan 25 at 1:14
  • 1
    $\begingroup$ Oh, my bad about the "induced subtree", I didn't realize that you wanted to accept skipping nodes! That is indeed a bit less common object, so just be sure to define it precisely when you use it, whatever name it ends up with (P.S. as a Frenchman I am contractually obligated to take offence at "Us Brits" :) $\endgroup$
    – Tassle
    Jan 25 at 8:58
  • $\begingroup$ @Tassle "I didn't realize that you wanted to accept skipping nodes!" Ah. Such is the problem of using English prose, my concise but imprecise wording "sparse subtree", rather than whatever the correct technical term is. :) As you say, "just be sure to define it precisely when you use it". :) To be clear, I've actually developed the most precise (though not concise!) definition I could in open collaboration with those who one would hope would know better than I. The brief version is "AST embedded in CST"; the full version is in a Q+A format at AST in CST. :) $\endgroup$
    – raiph
    Jan 25 at 10:59
  • $\begingroup$ PS "as a Frenchman I am contractually obligated to take offence at 'Us Brits'" 😊 As a tale of a trickster for whom details is a stickler // I must now note that what I wrote // implies not a bit the reader is a Brit // Though a bit, perhaps, is but a rhyming trap! //// I had reason to think you might be a Brit, but didn't know; Socrates said I should take creative advantage of the imprecision of English prose. And now I'll double down and say, presuming our shared appetite for idiomatic union, "Us Idiots just love whet whether, don't we?" Thx for being patient with our awful humour. 😊 $\endgroup$
    – raiph
    Jan 25 at 11:26

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.