Composite Pattern: Treating Tree Structures Through One Interface

Version note: The code in this post was built and run with C# 14 and .NET 10.

Guess First

Bookstore has started selling bundles. The Lord of the Rings trilogy is a bundle with a 10 percent discount; The Hobbit plus that trilogy is a larger collection with a 5 percent discount. So a bundle contains both books and another bundle. The first pricing code looks like this:

Book hobbit = new("978-0547928227", "The Hobbit", 14.00m);
Bundle trilogy = new("The Lord of the Rings Trilogy", 0.10m,
[
    new Book("978-0547928210", "The Fellowship of the Ring", 18.00m),
    new Book("978-0547928203", "The Two Towers", 18.00m),
    new Book("978-0547928197", "The Return of the King", 18.00m)
]);
Bundle collection = new("Middle-earth Collection", 0.05m, [hobbit, trilogy]);

Console.WriteLine($"Trilogy:    {PriceOf(trilogy)}");
Console.WriteLine($"Collection: {PriceOf(collection)}");

// The pricing code knows the shape of the tree itself
static decimal PriceOf(object item) => item switch
{
    Book book => book.Price,
    Bundle bundle => bundle.Items.OfType<Book>().Sum(b => b.Price) * (1 - bundle.Discount),
    _ => throw new ArgumentException($"Unknown item: {item}")
};

public sealed record Book(string Isbn, string Title, decimal Price);

public sealed record Bundle(string Name, decimal Discount, List<object> Items);

The trilogy's price should be 54 × 0.90 = 48.60. The collection's price is (14 + 48.60) × 0.95 = 59.47. What does the code print for each?

Part-Whole Hierarchies and the Cost of Type Checks

The output:

Trilogy:    48.6000
Collection: 13.3000

The trilogy is right, the collection is 13.30 instead of 59.47. OfType<Book>() silently filtered out the trilogy inside the bundle; only The Hobbit's discounted price was left. No exception, no warning, just a wrong number. Whoever wrote this code was probably thinking of single-level bundles, and for that day they were right.

The bigger problem is that this bug will repeat. Price, the number of books in the cart, shipping weight, stock checks, invoice lines: every operation working on the tree has to rewrite the same switch, the same recursion and the same "a bundle can contain a bundle" knowledge inside itself. The tree's structure has leaked into every client that uses it. List<object> has also cost us type safety: adding a string to a bundle compiles and only blows up when the price is computed.

The Composite Pattern: Component, Leaf and Composite

GoF (Gang of Four: the 1994 Design Patterns book by Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides) defines Composite's intent as composing objects into tree structures that represent part-whole hierarchies, and letting clients treat individual objects and compositions uniformly. The book's example is a drawing editor: simple shapes like lines, rectangles and text, and Picture, which groups them and behaves like a shape itself.

There are three roles. The component is the common interface of everything in the tree. The leaf is an end node with no children that does the work itself: for us, Book. The composite is the node that holds children and, when asked for an operation, delegates it to its children and combines the results: for us, Bundle. The key point of the pattern is that the composite also implements the component interface; that's how a bundle can be put inside another bundle just like a book.

Book hobbit = new("978-0547928227", "The Hobbit", 14.00m);
Bundle trilogy = new Bundle("The Lord of the Rings Trilogy", 0.10m)
    .Add(new Book("978-0547928210", "The Fellowship of the Ring", 18.00m))
    .Add(new Book("978-0547928203", "The Two Towers", 18.00m))
    .Add(new Book("978-0547928197", "The Return of the King", 18.00m));
Bundle collection = new Bundle("Middle-earth Collection", 0.05m).Add(hobbit).Add(trilogy);

// The client doesn't distinguish a single book from a bundle
foreach (ICatalogItem item in new ICatalogItem[] { hobbit, trilogy, collection })
    Console.WriteLine($"{item.Title,-30} {item.BookCount} book(s) {item.Price,7}");

Console.WriteLine();
collection.Print(Console.Out);

// Component: the shared contract of leaf and composite
public interface ICatalogItem
{
    string Title { get; }
    decimal Price { get; }
    int BookCount { get; }
    void Print(TextWriter writer, int depth = 0);
}

// Leaf: has no children, does the work itself
public sealed record Book(string Isbn, string Title, decimal Price) : ICatalogItem
{
    public int BookCount => 1;

    public void Print(TextWriter writer, int depth = 0) =>
        writer.WriteLine($"{new string(' ', depth * 2)}- {Title} ({Price})");
}

// Composite: delegates the work to its children and combines the result
public sealed class Bundle(string title, decimal discount) : ICatalogItem
{
    private readonly List<ICatalogItem> _items = [];

    public string Title => title;
    public IReadOnlyList<ICatalogItem> Items => _items;
    public decimal Price => decimal.Round(_items.Sum(i => i.Price) * (1 - discount), 2);
    public int BookCount => _items.Sum(i => i.BookCount);

    public Bundle Add(ICatalogItem item)
    {
        _items.Add(item);
        return this;
    }

    public void Print(TextWriter writer, int depth = 0)
    {
        writer.WriteLine($"{new string(' ', depth * 2)}+ {Title} (-{discount:P0}) = {Price}");
        foreach (ICatalogItem item in _items)
            item.Print(writer, depth + 1);
    }
}

The Hobbit                     1 book(s)   14.00
The Lord of the Rings Trilogy  3 book(s)   48.60
Middle-earth Collection        4 book(s)   59.47

+ Middle-earth Collection (-5%) = 59.47
  - The Hobbit (14.00)
  + The Lord of the Rings Trilogy (-10%) = 48.60
    - The Fellowship of the Ring (18.00)
    - The Two Towers (18.00)
    - The Return of the King (18.00)

The collection is now 59.47. There's no type check in Bundle.Price: it asks each child for its Price, the book returns its own price and the inner bundle returns its own discounted total. The recursion lives in the only place that knows the tree, inside the composite. The client loop treats the book, the trilogy and the collection as the same ICatalogItem; it doesn't need to know how deep the tree is. A new operation, say shipping weight, means one property on the interface, one value in the leaf and one Sum in the composite.

Applying and rounding the discount at every level is a deliberate decision too. A bundle's price is computed from its contents but has its own rule; the trilogy is 48.60 whether it's sold alone or inside the collection. Questions like which level the cent rounding happens at are covered in detail in the Solution Patterns series post "Money and Rounding".

Transparency or Safety?

Composite's most debated question is where the child-management methods (Add, Remove, Children) live. GoF describes both options and says it's a trade-off. If you choose transparency, you put these methods on the component: the client treats every node the same, but the leaf gets meaningless operations. If you choose safety, the methods live only on the composite: trying to add a child to a leaf doesn't compile, but the client has to know who it's talking to while building the tree. GoF's own sample code favors transparency. A transparent design and its result:

List<ICatalogItem> cart = [new Book("978-0547928227", "The Hobbit", 14.00m), new Bundle("Gift Box", 0.10m)];

// Admin screen: add a bookmark to every selected item
foreach (ICatalogItem item in cart)
{
    try
    {
        item.Add(new Book("000-0000000001", "Bookmark", 1.50m));
        Console.WriteLine($"{item.Title}: {item.Children.Count} item(s)");
    }
    catch (NotSupportedException ex)
    {
        Console.WriteLine($"{item.Title}: {ex.Message}");
    }
}

// Transparent design: child management lives in the component
public interface ICatalogItem
{
    string Title { get; }
    decimal Price { get; }
    IReadOnlyList<ICatalogItem> Children { get; }
    void Add(ICatalogItem item);
}

public sealed record Book(string Isbn, string Title, decimal Price) : ICatalogItem
{
    public IReadOnlyList<ICatalogItem> Children => [];

    // A meaningless operation for a leaf: the contract is there, the behavior isn't
    public void Add(ICatalogItem item) => throw new NotSupportedException("A book cannot contain other items.");
}

public sealed class Bundle(string title, decimal discount) : ICatalogItem
{
    private readonly List<ICatalogItem> _items = [];

    public string Title => title;
    public decimal Price => decimal.Round(_items.Sum(i => i.Price) * (1 - discount), 2);
    public IReadOnlyList<ICatalogItem> Children => _items;
    public void Add(ICatalogItem item) => _items.Add(item);
}

The Hobbit: A book cannot contain other items.
Gift Box: 1 item(s)

Book can't keep the promise the interface makes: the Add signature is there, but calling it throws. This is exactly the tension we examined in the SOLID (Single Responsibility, Open/Closed, Liskov Substitution, Interface Segregation, Dependency Inversion) and Design Principles series post "Liskov Substitution Principle: Behavioral Subtyping and NotSupportedException in .NET". In the safe design above, the same mistake is caught at compile time:

Book hobbit = new("978-0547928227", "The Hobbit", 14.00m);
hobbit.Add(new Book("000-0000000001", "Bookmark", 1.50m));

Program.cs(2,8): error CS1061: 'Book' does not contain a definition for 'Add' and no accessible extension method 'Add' accepting a first argument of type 'Book' could be found (are you missing a using directive or an assembly reference?)

The table's last row makes the choice easier: the code that really needs uniformity is the code using the tree, and it gets it in both designs. The code building the tree mostly knows what it's building anyway; the new Bundle(...).Add(...) chain works with the concrete type. In C#, choose safety by default; if a client that walks but doesn't modify the tree needs the children, a read-only Items or is Bundle bundle pattern matching is enough.

Composites in .NET

ASP.NET Core's configuration system is a textbook example of Composite. Both IConfigurationRoot and IConfigurationSection implement the IConfiguration interface; both return their subsections with GetChildren() and read values through the indexer. A section is itself a configuration:

using Microsoft.Extensions.Configuration;
using Microsoft.Extensions.Primitives;

IConfigurationRoot config = new ConfigurationBuilder()
    .AddInMemoryCollection(new Dictionary<string, string?>
    {
        ["Bookstore:Shipping:FreeAbove"] = "50",
        ["Bookstore:Shipping:Carriers:0"] = "Standard",
        ["Bookstore:Shipping:Carriers:1"] = "Express",
        ["Bookstore:Payments:DefaultProvider"] = "card"
    })
    .Build();

// Root and section are both IConfiguration: the same method walks both
PrintTree(config);
PrintTree(config.GetSection("Bookstore:Shipping"));

// Presenting several change tokens as a single token
using CancellationTokenSource pricesChanged = new();
using CancellationTokenSource stockChanged = new();
IChangeToken catalogChanged = new CompositeChangeToken(
[
    new CancellationChangeToken(pricesChanged.Token),
    new CancellationChangeToken(stockChanged.Token)
]);

using IDisposable registration = catalogChanged.RegisterChangeCallback(_ => Console.WriteLine("catalog cache invalidated"), null);
Console.WriteLine($"HasChanged: {catalogChanged.HasChanged}");
stockChanged.Cancel();
Console.WriteLine($"HasChanged: {catalogChanged.HasChanged}");

static void PrintTree(IConfiguration node, int depth = 0)
{
    foreach (IConfigurationSection child in node.GetChildren())
    {
        Console.WriteLine($"{new string(' ', depth * 2)}{child.Key}{(child.Value is null ? "" : $" = {child.Value}")}");
        PrintTree(child, depth + 1);
    }
}

Bookstore
  Payments
    DefaultProvider = card
  Shipping
    Carriers
      0 = Standard
      1 = Express
    FreeAbove = 50
Carriers
  0 = Standard
  1 = Express
FreeAbove = 50
HasChanged: False
catalog cache invalidated
HasChanged: True

PrintTree was called once with the root and once with the Bookstore:Shipping section, and the same code ran for both. The second half of the code shows another Composite: CompositeChangeToken presents several IChangeTokens as a single token; when one of the children changes, it counts as changed itself and fires its callback. Code that wants to clear the catalog cache when prices or stock change looks at one token instead of listening to two. The same family includes CompositeFileProvider: it presents several IFileProviders as one provider, tries them in order when a file is requested and returns the first file it finds. The ASP.NET Core Web API (Application Programming Interface) series post "Configuration and the Options Pattern in ASP.NET Core: Provider Order, User Secrets and Validation" covers the configuration side in detail.

Look closely and you'll see other trees in .NET too: expression trees in System.Linq.Expressions, XElement in System.Xml.Linq, Roslyn's syntax tree. There, Composite usually comes together with Iterator and Visitor: walking the tree and adding new operations to it. Those two are topics of the series' behavioral pattern posts.

Deep Trees and Cycles

Composite's recursion assumes the tree really is a tree. If bundles can be edited from an admin screen, that assumption breaks one day:

Bundle staffPicks = new("Staff Picks", 0.05m);
Bundle summerReads = new("Summer Reads", 0.10m);

summerReads.Add(new Book("978-0141439518", "Emma", 9.50m)).Add(staffPicks);
// Another admin adds "Summer Reads" to the "Staff Picks" bundle
staffPicks.Add(summerReads);

Console.WriteLine(staffPicks.Price);

The beginning and end of the output (50,567 lines in total; on macOS the process ended with exit code 134):

Stack overflow.
   at Bundle.get_Price()
   at Bundle+<>c.<get_Price>b__9_0(ICatalogItem)
   at Bundle.get_Price()
   at Bundle+<>c.<get_Price>b__9_0(ICatalogItem)
   ...
   at Bundle.get_Price()
   at Program.<Main>$(System.String[])

The two bundles contain each other; Price kept calling itself back and forth until the stack filled up. In .NET a stack overflow can't be caught: even with a try/catch, the process terminates. In a web application that means taking down not just the request but the whole application. The fix is to keep the cycle out of the tree in Add:

    public Bundle Add(ICatalogItem item)
    {
        // If the bundle being added already contains us, the tree becomes a cycle
        if (item is Bundle bundle && (bundle == this || bundle.Contains(this)))
            throw new InvalidOperationException($"'{bundle.Title}' already contains '{Title}'.");

        _items.Add(item);
        return this;
    }

    private bool Contains(ICatalogItem target) =>
        _items.Any(i => i == target || (i is Bundle child && child.Contains(target)));

'Summer Reads' already contains 'Staff Picks'.
8.55

The check itself is recursive and costs in proportion to the size of the tree; for small trees like catalog bundles that's negligible. In very deep trees (tens of thousands of levels, say an auto-generated chain) the recursion itself can be a problem; then the traversal has to be written iteratively with a Stack<T>. With real business data, such as an org chart or a category tree, the cycle check often belongs on the database side as well.

Storing the Tree in a Database

The in-memory Composite is independent of how the tree is stored in a relational database, in SQL (Structured Query Language) tables, but it's affected by it. The most common model is the adjacency list, where each row stores its ParentId; Entity Framework Core (EF Core) maps this with a self-referencing navigation. The problem is loading the whole tree: it's easy to end up writing an Include for every level or falling into N+1 queries with lazy loading. Recursive CTEs (Common Table Expressions), closure tables and SQL Server's hierarchyid type are different solutions to this problem; the Solution Patterns series post "Hierarchical Data in SQL: Adjacency List, Recursive CTE, Closure Table and hierarchyid" compares them. A practical route: fetch the tree as a flat list in a single query, build the composite in memory with a Dictionary<int, Bundle> and do the calculations on the in-memory tree.

Common Pitfalls

Putting meaningless methods on the leaf. Book.Add throwing an exception for the sake of transparency is an LSP (Liskov Substitution Principle) violation and a runtime trap. Put operations that need uniformity on the component, and tree building on the composite.

Caching a computed value in the composite and forgetting to invalidate it. Keeping Bundle.Price in a field is fast, but when the price of a book deep inside changes, the outer bundle has to find out. That means either a parent reference with upward notification (Observer) or recomputing every time. If the tree is small, recompute.

Leaving the parent reference inconsistent. If a child needs a reference to its parent (item.Parent), there should be one place that assigns it, inside Add and Remove only; otherwise an item ends up looking "parented" in two bundles at once.

Sharing the same item in two places without realizing it. In the example above, a single Book instance can be inside two bundles, and that's usually fine. But if the item is mutable, a change in one bundle shows up in the other too. Know whether you're building a tree or a graph with shared nodes.

Forcing every tree into Composite. Building a common interface for a two-level structure that will never get deeper (an order and its order lines) is needless abstraction. Composite's value shows where the depth is unknown and the client shouldn't have to tell a single item from a composition.

A Small Experiment

★☆☆ Add WeightGrams to ICatalogItem: a book has its own weight, a bundle adds 150 grams of packaging to the total of its contents. Print the collection's weight and count how many lines of code changed.

★★☆ Take the cycle check a step further: also prevent the same book from appearing twice in a bundle (the same ISBN (International Standard Book Number) even in different sub-bundles). Do you put the check in Add, or write a separate validation method? Why?

★★★ Write an IEnumerable<Book> Flatten() that walks all the books of a bundle without recursion, using a Stack<ICatalogItem>. Then build a chain 100,000 levels deep with a single bundle at each level and call both Price and Flatten().Count(). Which one worked?

Composite gave every node of the tree the same interface. In the next post we move to a pattern that also implements the same interface, but this time builds not a tree but a chain of wrappers: using Decorator to add caching, logging and retry behavior without touching the existing code.