Skip to content
LLD Learn/Structural Patterns
Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Composite: Trees & Hierarchies

5 min read

You'll learn to

  • -Model part-whole hierarchies (file systems, org charts, UI trees) so clients treat individual objects and groups uniformly
  • -Implement a Composite tree with a shared component interface for both leaf and container nodes
  • -Trace a recursive call through the tree to see why depth costs no extra code
  • -Decide where add() lives, and avoid the classic trap of cycles

Composite lets you compose objects into tree structures to represent part-whole hierarchies, and - the part that actually matters for interviews - lets client code treat individual objects (leaves) and compositions of objects (containers) uniformly through one shared interface.

An Analogy: Boxes Inside Boxes

Picture a shipping warehouse. A parcel can be a single item, or a box containing items, or a box containing other boxes. To work out the total weight you do not care which kind of thing you are looking at. You ask each thing for its weight: an item answers with its own weight, and a box answers with the sum of what is inside it. The person doing the weighing follows one rule for everything.

  • -The common question, what do you weigh, is the shared component interface.
  • -A single item is a leaf: it answers directly.
  • -A box is a container (composite): it answers by asking each thing inside it.
  • -A box inside a box needs no special code, because a box is just another thing that can be asked.

File System: The Canonical Example

A file system has Files (leaves, no children) and Directories (containers, which hold Files and other Directories). Both need to answer get_size() - a File returns its own size, a Directory returns the sum of its children's sizes. Composite defines a shared FileSystemComponent interface that both File and Directory implement, so any code computing total size never needs to know or check which kind of node it is looking at.

Leaves and containers, unified behind one interface
class FileSystemComponent(ABC):
    @abstractmethod
    def get_size(self) -> int: ...

class File(FileSystemComponent):          # leaf - no children
    def __init__(self, size: int):
        self._size = size
    def get_size(self) -> int:
        return self._size

class Directory(FileSystemComponent):      # container - holds other components
    def __init__(self):
        self._children: list[FileSystemComponent] = []
    def add(self, component: FileSystemComponent) -> None:
        self._children.append(component)
    def get_size(self) -> int:
        return sum(child.get_size() for child in self._children)  # recursion

root = Directory()
root.add(File(100))
sub = Directory()
sub.add(File(50))
root.add(sub)
root.get_size()  # 150 - works identically whether summing files or nested dirs

Tracing root.get_size()

  • -root is a Directory. It asks each child for get_size(): first File(100).
  • -The File answers 100 straight away: a leaf has nothing to recurse into.
  • -Next child is sub, another Directory. It asks its own children: File(50) answers 50.
  • -sub returns 50, and root adds 100 + 50 = 150.

The Recursive Structure Is the Whole Point

Notice that Directory.get_size() calls get_size() on each child without checking whether that child is a File or another Directory - it just trusts the shared interface. This is what makes Composite genuinely recursive and arbitrarily deep for free: a Directory ten levels deep computes its size correctly with the exact same code as a Directory one level deep, because every level of the tree honors the same contract.

Design Decisions Worth Naming

  • -Where does add() live? Put it on the shared interface and clients can treat everything uniformly, but a File then has an add() that must raise an error. Put it only on Directory and the interface is safe, but clients must check which kind of node they hold before adding. Interviewers like to hear you name this trade-off, uniformity against safety.
  • -Cycles: if a directory is added to itself, or to one of its own descendants, get_size() recurses for ever and raises a RecursionError. Guard add() against it, or keep each node's parent so you can check.
  • -Cost: get_size() visits every node each time. If it is called often and the tree rarely changes, cache the result in each container and clear it when a child changes.

Composite pairs naturally with any "part of a whole" LLD prompt: org charts (Employee vs. Manager, both answering get_headcount()), UI component trees (a Panel containing Buttons and other Panels), and menu systems are all the same underlying shape.

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!