If you view a tree as undirected graph without loops, then the opposite of that is just the same tree – it’s completely isomorphic.

If you speak about an actual data structure which uses directed graphs, then, again, it can be just named “tree” which has it’s links inverted: normally you have children referencing their parents (like is SQL database you’d have parent_id column referencing id column of the same table), but here you have parents have references of all their children. That would require having an array of references (parent->child), whereas in “normal” trees each element has just one reference (child->parent).

In git, for example, “true” merge commits have multiple parents, which is just what you’ve described. Although, git repository generally is not a tree, but some of its’ parts can be.

EDIT: from Wikipedia:

tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.

That means that parent-child relations in my git and SQL examples are actually considered inverted. As @Wyzard says, it is actually an “anti-tree” you’ve described. Yet, it is still called “tree”.

Inversion in these examples allows using just one reference (to a parent) per node instead of list of references (to children). Also, it is convenient to add children in one step, without having to add a reference into a children references list of its’ parent.

There sorta kind of is and isn’t! But we need to refine our terminology to understand what’s going on.

We have a hierarchy like this in graph theory, which flows from general at the top to more specific/restricted at the bottom:

Graph: a collection of nodes (vertex) and paths (connections between vertex)

Connected graph: a collection of nodes where you can pick any one start node and reach any other end node. The choice of start and end is arbitrary.

Tree: A connected graph where there is one and only one unique path between any one start node and any one end node. There are no alternate paths which do not backtrack (visit a node twice).

Rooted Tree: Just as a tree, but there is one specific item picked as being the root. From these we also define leaves, which is any node that must be an end-node when visited from the root – without visiting a node twice once you hit a leaf you cannot go anywhere, and the path is terminated. Leaves can also be called a “terminal vertex”.

Note that even a rooted tree does not necessarily have direction – you are free to start at a leaf and proceed to the root, etc.

If a tree is implemented as a single-linked data structure, this can be thought of as a directed tree if there is no back-link available – once you leave the root for one of the connected nodes, you can’t get back!

But such an implementation of a tree is not necessary in the definition of a tree! One can implement a tree with double-linked lists, such that you are free to do things like move towards the root (often referred to as a Parent) or away from the root (Child).

So if you want a data structure where you can start at a leaf and work to the root, you just need one that supports a “visit parent” function. You can also trivially define a system which does not permit moving from root (Parent) to Child, only from Child to Parent, and this sounds like what you are looking for. You basically just remove “visit child” functionality.

However, I am not aware of any formal name for such a structure, or what use such a structure would have. Trees that start from a root are useful, and ones that allow walking up and down are useful, but ones that only allow one-way movement towards the root is of such specialized/limited usefulness that I doubt it has a special name reserved for it. But I suppose anything is possible!

As a practical matter, you can easily implement one from existing directed trees or directed rooted trees.

I’m not sure of an exact mathematical concept for what you are describing, but it does seem to match pretty closely to the concept of a directed acyclic graph aka DAG. Many programmers actually use DAGs every day in their work, in the form of version control software. Git (and Mercurial and etc) commit histories form a DAG. We track the leaf nodes (in Git, the refs and branches; in Mercurial, the heads; etc) and traverse back to the root node. Each node has a pointer to to its parent, rather than the other way around.

A DAG does not need to be strictly tree-like in that it can have nodes with multiple parents (a merge commit in Git, for example).

I’m not really sure what the meaningful difference would be, nor how you would go about implementing such a thing. The two ways I have seen trees implemented is either with an array or a by reference.

In an array implementation, the first element is the root and child nodes can be located by a fairly simple transformation of the parent’s index. You could presumably reverse that easily enough so that the first element is the right most leaf and find the parent of any child by use of the array length and index. The only problem is that the array length and thus tree size is fixed and it is much harder to dynamically increase the size.

It’s much easier to do with references though. You could easily create an AntiTree class that, say, provides a list of all leaves, and then each leaf references it’s parent, and so on, until you reach the root which has no parent. But that just seems like a different traversal order.

Just had another thought. In terms of what to call it, isn’t what you are describing just a funnel?

From a purely technical standpoint, an anti-tree is what you have every time you choose to represent a tree not by equipping each parent node with an array of pointers to its child nodes, but by equipping each child node with a single pointer to its parent node.

Trees are commonly represented this way, for example, in relational databases.