Baumstrukturen sind in der Informatik allgegenwärtig: Dateisysteme, HTML-DOM, Kategorie-Hierarchien, Syntaxbäume. Das natürlichste Werkzeug, um sie zu durchsuchen, sind rekursive Algorithmen – Funktionen, die sich selbst aufrufen, um tiefere Ebenen zu erkunden.

Was ist Rekursion?

Rekursion bedeutet, dass eine Funktion sich selbst aufruft. Jeder rekursive Aufruf bearbeitet einen kleineren Teil des Problems, bis ein Basisfall erreicht wird, der keine weitere Rekursion erfordert. Ohne Basisfall gibt es eine unendliche Schleife – den Stack Overflow.

Preorder Tree Traversal in Python

class TreeNode:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

def preorder_traversal(node, depth=0):
    # Preorder: Knoten besuchen, dann Kinder
    print("  " * depth + str(node.value))
    for child in node.children:
        preorder_traversal(child, depth + 1)

# Beispiel-Baum
root = TreeNode("root", [
    TreeNode("A", [TreeNode("A1"), TreeNode("A2")]),
    TreeNode("B", [TreeNode("B1")])
])
preorder_traversal(root)

Anwendung: Kategorien-Hierarchie in SQL

-- Rekursive CTE in SQL für Kategorie-Hierarchie
WITH CategoryTree AS (
    -- Basisfall: Root-Kategorien
    SELECT id, name, parent_id, 0 AS level
    FROM categories WHERE parent_id IS NULL

    UNION ALL

    -- Rekursiver Teil: Kinder
    SELECT c.id, c.name, c.parent_id, ct.level + 1
    FROM categories c
    JOIN CategoryTree ct ON c.parent_id = ct.id
)
SELECT REPLICATE('  ', level) + name AS tree_view
FROM CategoryTree
ORDER BY id;

Rekursive Algorithmen sind elegant für Baumprobleme, aber man muss die Stack-Tiefe im Auge behalten. Bei sehr tiefen Bäumen (>1000 Ebenen) kann es zu Stack Overflows kommen – in diesem Fall ist eine iterative Lösung mit explizitem Stack robuster.