Some data repeats its own shape. A text tree can be one string, a list of text trees, or a tuple of text trees. Structural recursion follows that definition: solve a leaf directly, otherwise solve each child subtree and combine the results. This is more than a function calling itself. It needs a base case, a progress argument and a clear rule for combining returned values.
Our trees are finite, acyclic and bounded to thirty nested containers. Moving to a child therefore reduces the remaining structure along that path. An empty branch also terminates because there are no child calls. A repeated reference is allowed, but it represents a repeated occurrence; the walk does not silently deduplicate it.
Recognize strings before treating a value as a branch. Strings are iterable too, yet the contract defines the whole string as one leaf. Recursing over characters would change the meaning and can recurse forever on a one-character string. An empty string is a valid leaf, while an empty list or tuple has no leaves.
def leaves(tree):
if isinstance(tree, str):
return (tree,)
if not isinstance(tree, (list, tuple)):
raise ValueError("unsupported leaf")
return tuple(word for child in tree for word in leaves(child))
print(leaves(["a", ["b", ()], ""]))
print(leaves("whole string"))Each recursive invocation has its own local variables. A parent waits for a child result, then continues with the next child. There is no need for a shared global result list, which would complicate repeated calls, independent uses and exception handling. A local list plus extend is often clearer than the nested comprehension shown above.
Flattening and mapping combine child results differently. flatten_text joins all returned leaf tuples into one flat tuple, discarding branch shape. map_tree retains each branch position, converts branches to tuples, and invokes the supplied transform exactly once per string leaf. Empty branches survive mapping as empty tuples, while flattening contributes no leaves for them.
def map_tree(tree, change):
if isinstance(tree, str):
return change(tree)
if not isinstance(tree, (list, tuple)):
raise ValueError("unsupported leaf")
return tuple(map_tree(child, change) for child in tree)
print(map_tree(["oak", ["elm", []]], str.upper))Unsupported values raise ValueError rather than being silently stringified. A callback error propagates immediately; later leaves are not processed. Already-performed callback effects are not undone, so ordinary policies should preserve inputs. A failed pure transformation returns no partial result, even though a deliberately observable test callback can reveal which prefix was visited.
CPython retains recursive frames and has a recursion limit. This bounded tree walk does not promise unlimited depth, tail-call optimization, cycle detection or linear memory for every flattening strategy. Repeatedly concatenating large partial results can copy data more than once; a later lazy traversal can avoid retaining all leaves at each level. First establish the correct structural model.
For practice, trace the order of a nested tree containing an empty string, an empty container and an aliased subtree. The build tests those cases, callback order, unsupported leaves and a reasonably deep bounded tree. The bug hunts distinguish adding a child tuple as one element from extending with its individual leaves.