# What would we call this datastructure?

Suppose we have a datastructure that is a list containing elements that are either a leaf or another layer of the datastructure (recursively defined). What would we call this? It isn't a tree, since it has variable number of leaves and branches on each node. It isn't a forest, since it doesn't consist of a list of trees. I'm not exactly sure what to call it.

For context, the specific structure I'm designing is used as part of a compiler. The language is indentation structured, so blocks of code are grouped by their indentation level.

I have an Indentation_______, which is a list of nodes where the node is either a statement in the program, or a new Indentation_______ containing the next nested indentation level.

Any ideas?

-
It is actually a tree. Just not a binary tree (or n-ary tree). But it's still a tree. – Wildcard Jan 13 at 1:39
I prefer to call these things blocks but ... – Joshua Jan 13 at 5:29

A tree is not restricted to a certain branching factor. A n-ary tree may only have a branching factor of n (or less), but in an unrestricted tree, each node may contain an arbitrary number of subnodes.

A tree is a connected graph without cycles, so your datastructure still satisfies that definition.

Alternatively you could call your structure something like "nested lists".

-
(nit): "A tree is a [connected] graph without cycles" – Mike B. Jan 12 at 14:24
@MikeB. thanks, I added that – user3158988 Jan 12 at 14:27
Technically, even a linked list is a degenerate tree. – chrylis Jan 12 at 18:37
Most trees in CS are technically rooted, ordered trees. Not trees at all for graph theory purists – vonbrand Jan 13 at 1:32

The set of

• rooted trees with
• arbitrary numbers of children
• the order of which matters

is typically called the set of plane trees or simply ordered trees (the absence of further restrictions characterises the set sufficiently).

So feel free to use "tree" provided you clarify (once) which kind you mean exactly. The only possible point of confusion is the separation from graph-theoretic trees, which are not necessarily rooted.

-