Return a list of all objects vertically stacked above a given object?

Question

For input to a physics program I am building layers stacked on each other. For each layer more than one object can be stacked, so the physical result will look like the drawing below.

The example script shows how I'd like to build these stacks, and I want to generate a list of tuples, each tuple contains objects that are stacked vertically started from the bottom.

Calling get_stacks() on any object will return the stacks that are on it.

I've managed to avoid understanding recursion for years, but now it's time to learn. Is there a simple way to do this?

class Thing():
    def __init__(self, name):
        self.name = name
        self.things = []
    def add(self, name):
        thing = Thing(name)
        self.things.append(thing)
        return thing
    def __repr__(self):
        return ('{self.name}'.format(self=self))
    def get_stacks(self):    
        "generates a list of tuples of vertically stacked objects"
        stacks = []
        # What do I do here to get a list of tuples of objects?
        return stacks

S = Thing('S')
C = S.add('A').add('B').add('C')
D = S.add('D')
E = D.add('E')
F = D.add('F')

print(S.get_stacks()) # expect [('S', 'A', 'B', 'C'), ('S', 'D', 'E'), ('S', 'D', 'F')]

print(D.get_stacks()) # expect [('D', 'E'), ('D', 'F')]

print(C.get_stacks()) # expect [('C',)]

#  ------------
# |      C     |
#  ------------------------
# |      B     |  E  |  F  |
#  ------------------------
# |      A     |     D     |
#  ------------------------
# |        Substrate       |
#  ------------------------

Answer 1

Your puzzle relates to Tree traversal with defined children elements. You should try to go to any possible way (thing in your case) and save the result if there're no things there. In there are things, you don't save the current path into the stack and should go further recursively, storing your current path somewhere. Below I wrote a quick solution how you can reach the result in your particular case. You can also improve your code, storing parent in your class, or something else. There're many ways.

def get_stacks(self):
    stacks = []

    def __fill_stacks(stacks, thing, path):
        for th in thing.things:
            __fill_stacks(stacks, th, path + [thing.name])
        if not thing.things:
            stacks.append(path + [thing.name])

    __fill_stacks(stacks, self, [])

    return stacks