Iterator & Composite Pattern - Traversal Abstractions

🎯

Iterator & Composite Pattern - Traversal Abstractions

mediumOOPAmazonGoogleMicrosoft

Imagine you have a complex file system with folders containing files and other folders. You want a uniform way to traverse all files and folders without worrying about their internal structure.

💡 This problem introduces how to abstract traversal over complex hierarchical structures using design patterns. Beginners often struggle because they try to handle traversal logic manually, mixing concerns of structure and iteration, leading to rigid and error-prone code.

📋

Problem Statement

Design and implement traversal abstractions over a tree-like composite structure using the Iterator and Composite design patterns. The goal is to provide a uniform way to traverse all elements (both composite nodes and leaf nodes) without exposing the internal structure of the composite. Implement iterators that allow clients to traverse the composite structure transparently.

The composite structure can be arbitrarily deep.Traversal should be uniform and not expose internal details.Iterator should support standard iteration operations (hasNext, next).Composite nodes can contain zero or more child components.

💡

Example

Input"Composite root with children: Folder1 (FileA, FileB), Folder2 (FileC)"

OutputTraversal order: Folder1, FileA, FileB, Folder2, FileC

The iterator traverses the composite tree in a depth-first manner, visiting each folder and its files.

• Empty composite (no children) → iterator returns no elements
• Composite with only leaf nodes → iterator returns all leaves
• Deeply nested composites → iterator correctly traverses all levels
• Composite with mixed leaf and composite children → iterator handles both transparently

⚠️

Common Mistakes

Mixing traversal logic inside composite nodes

Code becomes tightly coupled and hard to extend or reuse

✅ Separate traversal into iterator classes or interfaces

Not pushing children in reverse order in stack-based iterator

Traversal order is reversed or incorrect

✅ Push children onto stack in reverse order to maintain correct traversal sequence

Failing to implement hasNext correctly in iterators

next() may throw unexpectedly or infinite loops occur

✅ Ensure hasNext accurately reflects if more elements remain

Not handling empty composites or leaves in iterators

Iterator may crash or return invalid elements

✅ Add checks for empty children and handle leaf iterators properly

Using recursion without limits on deep trees

Stack overflow on very deep composite structures

✅ Use iterative traversal with explicit stack in iterator

🧠

Brute Force (Manual Recursive Traversal)

💡 Starting with a manual recursive traversal helps understand the problem deeply by explicitly handling each node type and recursion, before abstracting with patterns.

Intuition

Traverse the composite tree by recursively visiting each node and its children, printing or processing nodes as you go.

Algorithm

1. Start at the root component.
2. If the component is a leaf, process it directly.
3. If the component is composite, recursively traverse each child.
4. Continue until all nodes are visited.

💡 This approach is straightforward but mixes traversal logic with structure, making it hard to extend or reuse.

</>

Code

class Component:
    def __init__(self, name):
        self.name = name

class Leaf(Component):
    def __init__(self, name):
        super().__init__(name)

class Composite(Component):
    def __init__(self, name):
        super().__init__(name)
        self.children = []
    def add(self, component):
        self.children.append(component)

def traverse(component):
    if isinstance(component, Leaf):
        print(f"Leaf: {component.name}")
    elif isinstance(component, Composite):
        print(f"Composite: {component.name}")
        for child in component.children:
            traverse(child)

# Driver code
if __name__ == '__main__':
    root = Composite('root')
    folder1 = Composite('Folder1')
    folder1.add(Leaf('FileA'))
    folder1.add(Leaf('FileB'))
    folder2 = Composite('Folder2')
    folder2.add(Leaf('FileC'))
    root.add(folder1)
    root.add(folder2)
    traverse(root)

Line Notes

class Component:Defines the base class for all components in the composite structure

def traverse(component):Recursive function to visit each node in the composite tree

if isinstance(component, Leaf):Base case: process leaf nodes directly

for child in component.children:Recursively traverse all children of a composite node

import java.util.*;

abstract class Component {
    String name;
    Component(String name) { this.name = name; }
}

class Leaf extends Component {
    Leaf(String name) { super(name); }
}

class Composite extends Component {
    List<Component> children = new ArrayList<>();
    Composite(String name) { super(name); }
    void add(Component c) { children.add(c); }
}

public class Main {
    static void traverse(Component c) {
        if (c instanceof Leaf) {
            System.out.println("Leaf: " + c.name);
        } else if (c instanceof Composite) {
            System.out.println("Composite: " + c.name);
            for (Component child : ((Composite) c).children) {
                traverse(child);
            }
        }
    }
    public static void main(String[] args) {
        Composite root = new Composite("root");
        Composite folder1 = new Composite("Folder1");
        folder1.add(new Leaf("FileA"));
        folder1.add(new Leaf("FileB"));
        Composite folder2 = new Composite("Folder2");
        folder2.add(new Leaf("FileC"));
        root.add(folder1);
        root.add(folder2);
        traverse(root);
    }
}

Line Notes

abstract class Component {Base class for all components in the composite pattern

static void traverse(Component c) {Recursive traversal method visiting each node

if (c instanceof Leaf) {Process leaf nodes directly

for (Component child : ((Composite) c).children) {Recursively traverse composite children

#include <iostream>
#include <vector>
#include <memory>
using namespace std;

class Component {
public:
    string name;
    Component(string n) : name(n) {}
    virtual ~Component() {}
};

class Leaf : public Component {
public:
    Leaf(string n) : Component(n) {}
};

class Composite : public Component {
public:
    vector<shared_ptr<Component>> children;
    Composite(string n) : Component(n) {}
    void add(shared_ptr<Component> c) { children.push_back(c); }
};

void traverse(shared_ptr<Component> c) {
    if (dynamic_cast<Leaf*>(c.get())) {
        cout << "Leaf: " << c->name << endl;
    } else if (auto comp = dynamic_cast<Composite*>(c.get())) {
        cout << "Composite: " << comp->name << endl;
        for (auto& child : comp->children) {
            traverse(child);
        }
    }
}

int main() {
    auto root = make_shared<Composite>("root");
    auto folder1 = make_shared<Composite>("Folder1");
    folder1->add(make_shared<Leaf>("FileA"));
    folder1->add(make_shared<Leaf>("FileB"));
    auto folder2 = make_shared<Composite>("Folder2");
    folder2->add(make_shared<Leaf>("FileC"));
    root->add(folder1);
    root->add(folder2);
    traverse(root);
    return 0;
}

Line Notes

class Component {Base class for composite pattern components

void traverse(shared_ptr<Component> c) {Recursive traversal function for composite tree

if (dynamic_cast<Leaf*>(c.get())) {Check if current node is a leaf

for (auto& child : comp->children) {Recursively traverse composite children

class Component {
  constructor(name) {
    this.name = name;
  }
}

class Leaf extends Component {
  constructor(name) {
    super(name);
  }
}

class Composite extends Component {
  constructor(name) {
    super(name);
    this.children = [];
  }
  add(component) {
    this.children.push(component);
  }
}

function traverse(component) {
  if (component instanceof Leaf) {
    console.log(`Leaf: ${component.name}`);
  } else if (component instanceof Composite) {
    console.log(`Composite: ${component.name}`);
    component.children.forEach(child => traverse(child));
  }
}

// Driver code
const root = new Composite('root');
const folder1 = new Composite('Folder1');
folder1.add(new Leaf('FileA'));
folder1.add(new Leaf('FileB'));
const folder2 = new Composite('Folder2');
folder2.add(new Leaf('FileC'));
root.add(folder1);
root.add(folder2);
traverse(root);

Line Notes

class Component {Defines base class for all components

function traverse(component) {Recursive traversal function for composite structure

if (component instanceof Leaf) {Process leaf nodes directly

component.children.forEach(child => traverse(child));Recursively traverse composite children

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once, where n is total nodes. Space is due to recursion stack up to height h.

💡 For 1000 nodes with height 10, expect about 1000 operations and stack depth 10.

Interview Verdict: Accepted

This approach works but tightly couples traversal with structure, making it less flexible for extension.

🧠

Iterator Pattern Implementation (Explicit Iterator Class)

💡 This approach abstracts traversal logic into an iterator class, separating iteration from the composite structure, improving modularity and reusability.

Intuition

Create an iterator that maintains a stack of nodes to visit, yielding one element at a time, hiding recursion from the client.

Algorithm

1. Initialize a stack with the root component.
2. On next(), pop the top component from the stack.
3. If the component is composite, push its children onto the stack in reverse order.
4. Return the popped component; repeat until stack is empty.

💡 This simulates depth-first traversal iteratively, avoiding recursion and exposing a standard iterator interface.

</>

Code

class Component:
    def __init__(self, name):
        self.name = name

class Leaf(Component):
    def __init__(self, name):
        super().__init__(name)

class Composite(Component):
    def __init__(self, name):
        super().__init__(name)
        self.children = []
    def add(self, component):
        self.children.append(component)

class CompositeIterator:
    def __init__(self, root):
        self.stack = [root]

    def __iter__(self):
        return self

    def __next__(self):
        if not self.stack:
            raise StopIteration
        current = self.stack.pop()
        if isinstance(current, Composite):
            for child in reversed(current.children):
                self.stack.append(child)
        return current

# Driver code
if __name__ == '__main__':
    root = Composite('root')
    folder1 = Composite('Folder1')
    folder1.add(Leaf('FileA'))
    folder1.add(Leaf('FileB'))
    folder2 = Composite('Folder2')
    folder2.add(Leaf('FileC'))
    root.add(folder1)
    root.add(folder2)

    iterator = CompositeIterator(root)
    for component in iterator:
        if isinstance(component, Composite):
            print(f"Composite: {component.name}")
        else:
            print(f"Leaf: {component.name}")

Line Notes

class CompositeIterator:Defines an iterator class encapsulating traversal state

self.stack = [root]Initialize stack with root to start traversal

def __next__(self):Returns next element in traversal or raises StopIteration

for child in reversed(current.children):Push children in reverse to maintain correct traversal order

import java.util.*;

abstract class Component {
    String name;
    Component(String name) { this.name = name; }
}

class Leaf extends Component {
    Leaf(String name) { super(name); }
}

class Composite extends Component {
    List<Component> children = new ArrayList<>();
    Composite(String name) { super(name); }
    void add(Component c) { children.add(c); }
}

class CompositeIterator implements Iterator<Component> {
    private Stack<Component> stack = new Stack<>();
    CompositeIterator(Component root) { stack.push(root); }

    public boolean hasNext() { return !stack.isEmpty(); }

    public Component next() {
        if (!hasNext()) throw new NoSuchElementException();
        Component current = stack.pop();
        if (current instanceof Composite) {
            List<Component> children = ((Composite) current).children;
            for (int i = children.size() - 1; i >= 0; i--) {
                stack.push(children.get(i));
            }
        }
        return current;
    }
}

public class Main {
    public static void main(String[] args) {
        Composite root = new Composite("root");
        Composite folder1 = new Composite("Folder1");
        folder1.add(new Leaf("FileA"));
        folder1.add(new Leaf("FileB"));
        Composite folder2 = new Composite("Folder2");
        folder2.add(new Leaf("FileC"));
        root.add(folder1);
        root.add(folder2);

        CompositeIterator iterator = new CompositeIterator(root);
        while (iterator.hasNext()) {
            Component c = iterator.next();
            if (c instanceof Composite) {
                System.out.println("Composite: " + c.name);
            } else {
                System.out.println("Leaf: " + c.name);
            }
        }
    }
}

Line Notes

class CompositeIterator implements Iterator<Component> {Iterator class encapsulating traversal logic

private Stack<Component> stack = new Stack<>();Stack to hold nodes to visit next

public Component next() {Returns next element in traversal

for (int i = children.size() - 1; i >= 0; i--) {Push children in reverse order to maintain traversal order

#include <iostream>
#include <vector>
#include <stack>
#include <memory>
using namespace std;

class Component {
public:
    string name;
    Component(string n) : name(n) {}
    virtual ~Component() {}
};

class Leaf : public Component {
public:
    Leaf(string n) : Component(n) {}
};

class Composite : public Component {
public:
    vector<shared_ptr<Component>> children;
    Composite(string n) : Component(n) {}
    void add(shared_ptr<Component> c) { children.push_back(c); }
};

class CompositeIterator {
    stack<shared_ptr<Component>> stk;
public:
    CompositeIterator(shared_ptr<Component> root) { stk.push(root); }
    bool hasNext() { return !stk.empty(); }
    shared_ptr<Component> next() {
        if (stk.empty()) throw runtime_error("No more elements");
        auto current = stk.top();
        stk.pop();
        if (auto comp = dynamic_cast<Composite*>(current.get())) {
            for (auto it = comp->children.rbegin(); it != comp->children.rend(); ++it) {
                stk.push(*it);
            }
        }
        return current;
    }
};

int main() {
    auto root = make_shared<Composite>("root");
    auto folder1 = make_shared<Composite>("Folder1");
    folder1->add(make_shared<Leaf>("FileA"));
    folder1->add(make_shared<Leaf>("FileB"));
    auto folder2 = make_shared<Composite>("Folder2");
    folder2->add(make_shared<Leaf>("FileC"));
    root->add(folder1);
    root->add(folder2);

    CompositeIterator it(root);
    while (it.hasNext()) {
        auto c = it.next();
        if (dynamic_cast<Composite*>(c.get())) {
            cout << "Composite: " << c->name << endl;
        } else {
            cout << "Leaf: " << c->name << endl;
        }
    }
    return 0;
}

Line Notes

class CompositeIterator {Iterator class encapsulating traversal state

stack<shared_ptr<Component>> stk;Stack to hold nodes for traversal

shared_ptr<Component> next() {Returns next element in traversal

for (auto it = comp->children.rbegin(); it != comp->children.rend(); ++it) {Push children in reverse order to maintain correct traversal

class Component {
  constructor(name) {
    this.name = name;
  }
}

class Leaf extends Component {
  constructor(name) {
    super(name);
  }
}

class Composite extends Component {
  constructor(name) {
    super(name);
    this.children = [];
  }
  add(component) {
    this.children.push(component);
  }
}

class CompositeIterator {
  constructor(root) {
    this.stack = [root];
  }
  hasNext() {
    return this.stack.length > 0;
  }
  next() {
    if (!this.hasNext()) throw new Error('No more elements');
    const current = this.stack.pop();
    if (current instanceof Composite) {
      for (let i = current.children.length - 1; i >= 0; i--) {
        this.stack.push(current.children[i]);
      }
    }
    return current;
  }
}

// Driver code
const root = new Composite('root');
const folder1 = new Composite('Folder1');
folder1.add(new Leaf('FileA'));
folder1.add(new Leaf('FileB'));
const folder2 = new Composite('Folder2');
folder2.add(new Leaf('FileC'));
root.add(folder1);
root.add(folder2);

const iterator = new CompositeIterator(root);
while (iterator.hasNext()) {
  const c = iterator.next();
  if (c instanceof Composite) {
    console.log(`Composite: ${c.name}`);
  } else {
    console.log(`Leaf: ${c.name}`);
  }
}

Line Notes

class CompositeIterator {Iterator class encapsulating traversal logic

this.stack = [root];Initialize stack with root node

next() {Returns next element in traversal or throws error if done

for (let i = current.children.length - 1; i >= 0; i--) {Push children in reverse order to maintain traversal order

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once; stack size bounded by tree height h.

💡 For 1000 nodes with height 10, expect about 1000 operations and stack size up to 10.

Interview Verdict: Accepted

This approach cleanly separates traversal from structure, improving code maintainability and testability.

🧠

Composite Pattern with Iterator Interface (Unified Component Iterator)

💡 This approach integrates the iterator interface directly into the composite components, allowing clients to get iterators from any component transparently.

Intuition

Each component provides its own iterator; leaf returns a simple iterator over itself, composite returns an iterator that traverses its children recursively.

Algorithm

1. Define an iterator interface with hasNext and next methods.
2. Leaf component returns an iterator yielding itself once.
3. Composite component returns an iterator that iterates over its children’s iterators recursively.
4. Clients use the iterator interface uniformly without type checks.

💡 This approach maximizes encapsulation and polymorphism, making traversal extensible and transparent.

</>

Code

from collections import deque

class Iterator:
    def hasNext(self):
        raise NotImplementedError
    def next(self):
        raise NotImplementedError

class Component:
    def __init__(self, name):
        self.name = name
    def create_iterator(self):
        raise NotImplementedError

class Leaf(Component):
    def create_iterator(self):
        return LeafIterator(self)

class Composite(Component):
    def __init__(self, name):
        super().__init__(name)
        self.children = []
    def add(self, component):
        self.children.append(component)
    def create_iterator(self):
        return CompositeIterator(self.children)

class LeafIterator(Iterator):
    def __init__(self, leaf):
        self.leaf = leaf
        self.done = False
    def hasNext(self):
        return not self.done
    def next(self):
        if self.done:
            raise StopIteration
        self.done = True
        return self.leaf

class CompositeIterator(Iterator):
    def __init__(self, children):
        self.stack = deque()
        self.children = children
        self.index = 0
        self.current_iterator = None
    def hasNext(self):
        while True:
            if self.current_iterator is None:
                if self.index >= len(self.children):
                    return False
                self.current_iterator = self.children[self.index].create_iterator()
                self.index += 1
            if self.current_iterator.hasNext():
                return True
            else:
                self.current_iterator = None
    def next(self):
        if not self.hasNext():
            raise StopIteration
        return self.current_iterator.next()

# Driver code
if __name__ == '__main__':
    root = Composite('root')
    folder1 = Composite('Folder1')
    folder1.add(Leaf('FileA'))
    folder1.add(Leaf('FileB'))
    folder2 = Composite('Folder2')
    folder2.add(Leaf('FileC'))
    root.add(folder1)
    root.add(folder2)

    iterator = root.create_iterator()
    while iterator.hasNext():
        component = iterator.next()
        if isinstance(component, Composite):
            print(f"Composite: {component.name}")
        else:
            print(f"Leaf: {component.name}")

Line Notes

class Component:Base component class with iterator factory method

def create_iterator(self):Abstract method to get iterator for component

class LeafIterator(Iterator):Iterator for leaf nodes yielding itself once

class CompositeIterator(Iterator):Iterator for composite nodes iterating over children iterators

import java.util.*;

interface Iterator<T> {
    boolean hasNext();
    T next();
}

abstract class Component {
    String name;
    Component(String name) { this.name = name; }
    abstract Iterator<Component> createIterator();
}

class Leaf extends Component {
    Leaf(String name) { super(name); }
    public Iterator<Component> createIterator() {
        return new LeafIterator(this);
    }
}

class Composite extends Component {
    List<Component> children = new ArrayList<>();
    Composite(String name) { super(name); }
    void add(Component c) { children.add(c); }
    public Iterator<Component> createIterator() {
        return new CompositeIterator(children);
    }
}

class LeafIterator implements Iterator<Component> {
    private Leaf leaf;
    private boolean done = false;
    LeafIterator(Leaf leaf) { this.leaf = leaf; }
    public boolean hasNext() { return !done; }
    public Component next() {
        if (done) throw new NoSuchElementException();
        done = true;
        return leaf;
    }
}

class CompositeIterator implements Iterator<Component> {
    private List<Component> children;
    private int index = 0;
    private Iterator<Component> currentIterator = null;
    CompositeIterator(List<Component> children) { this.children = children; }
    public boolean hasNext() {
        while (true) {
            if (currentIterator == null) {
                if (index >= children.size()) return false;
                currentIterator = children.get(index).createIterator();
                index++;
            }
            if (currentIterator.hasNext()) return true;
            else currentIterator = null;
        }
    }
    public Component next() {
        if (!hasNext()) throw new NoSuchElementException();
        return currentIterator.next();
    }
}

public class Main {
    public static void main(String[] args) {
        Composite root = new Composite("root");
        Composite folder1 = new Composite("Folder1");
        folder1.add(new Leaf("FileA"));
        folder1.add(new Leaf("FileB"));
        Composite folder2 = new Composite("Folder2");
        folder2.add(new Leaf("FileC"));
        root.add(folder1);
        root.add(folder2);

        Iterator<Component> iterator = root.createIterator();
        while (iterator.hasNext()) {
            Component c = iterator.next();
            if (c instanceof Composite) {
                System.out.println("Composite: " + c.name);
            } else {
                System.out.println("Leaf: " + c.name);
            }
        }
    }
}

Line Notes

abstract class Component {Base component with abstract iterator factory

abstract Iterator<Component> createIterator();Each component provides its own iterator

class LeafIterator implements Iterator<Component> {Iterator for leaf nodes yielding itself once

class CompositeIterator implements Iterator<Component> {Iterator for composite nodes iterating over children iterators

#include <iostream>
#include <vector>
#include <memory>
#include <stdexcept>
#include <deque>
using namespace std;

class Iterator {
public:
    virtual bool hasNext() = 0;
    virtual shared_ptr<class Component> next() = 0;
    virtual ~Iterator() {}
};

class Component : public enable_shared_from_this<Component> {
public:
    string name;
    Component(string n) : name(n) {}
    virtual shared_ptr<Iterator> createIterator() = 0;
    virtual ~Component() {}
};

class Leaf : public Component, public enable_shared_from_this<Leaf> {
public:
    Leaf(string n) : Component(n) {}

    class LeafIterator : public Iterator {
        bool done = false;
        shared_ptr<Leaf> leaf;
    public:
        LeafIterator(shared_ptr<Leaf> l) : leaf(l) {}
        bool hasNext() override { return !done; }
        shared_ptr<Component> next() override {
            if (done) throw runtime_error("No more elements");
            done = true;
            return leaf;
        }
    };

    shared_ptr<Iterator> createIterator() override {
        return make_shared<LeafIterator>(static_pointer_cast<Leaf>(shared_from_this()));
    }
};

class Composite : public Component, public enable_shared_from_this<Composite> {
public:
    vector<shared_ptr<Component>> children;
    Composite(string n) : Component(n) {}
    void add(shared_ptr<Component> c) { children.push_back(c); }

    class CompositeIterator : public Iterator {
        vector<shared_ptr<Component>> children;
        size_t index = 0;
        shared_ptr<Iterator> currentIterator = nullptr;
    public:
        CompositeIterator(vector<shared_ptr<Component>> c) : children(c) {}
        bool hasNext() override {
            while (true) {
                if (!currentIterator) {
                    if (index >= children.size()) return false;
                    currentIterator = children[index++]->createIterator();
                }
                if (currentIterator->hasNext()) return true;
                else currentIterator = nullptr;
            }
        }
        shared_ptr<Component> next() override {
            if (!hasNext()) throw runtime_error("No more elements");
            return currentIterator->next();
        }
    };

    shared_ptr<Iterator> createIterator() override {
        return make_shared<CompositeIterator>(children);
    }
};

int main() {
    auto root = make_shared<Composite>("root");
    auto folder1 = make_shared<Composite>("Folder1");
    folder1->add(make_shared<Leaf>("FileA"));
    folder1->add(make_shared<Leaf>("FileB"));
    auto folder2 = make_shared<Composite>("Folder2");
    folder2->add(make_shared<Leaf>("FileC"));
    root->add(folder1);
    root->add(folder2);

    auto iterator = root->createIterator();
    while (iterator->hasNext()) {
        auto c = iterator->next();
        if (dynamic_cast<Composite*>(c.get())) {
            cout << "Composite: " << c->name << endl;
        } else {
            cout << "Leaf: " << c->name << endl;
        }
    }
    return 0;
}

Line Notes

class Component : public enable_shared_from_this<Component> {Abstract base component with iterator factory and shared_from_this support

class Leaf : public Component, public enable_shared_from_this<Leaf> {Leaf class inherits enable_shared_from_this for safe shared pointer creation

class LeafIterator : public Iterator {Iterator for leaf nodes yielding itself once

class CompositeIterator : public Iterator {Iterator for composite nodes iterating over children iterators

class Iterator {
  hasNext() { throw new Error('Not implemented'); }
  next() { throw new Error('Not implemented'); }
}

class Component {
  constructor(name) {
    this.name = name;
  }
  createIterator() { throw new Error('Not implemented'); }
}

class Leaf extends Component {
  createIterator() {
    return new LeafIterator(this);
  }
}

class Composite extends Component {
  constructor(name) {
    super(name);
    this.children = [];
  }
  add(component) {
    this.children.push(component);
  }
  createIterator() {
    return new CompositeIterator(this.children);
  }
}

class LeafIterator extends Iterator {
  constructor(leaf) {
    super();
    this.leaf = leaf;
    this.done = false;
  }
  hasNext() {
    return !this.done;
  }
  next() {
    if (this.done) throw new Error('No more elements');
    this.done = true;
    return this.leaf;
  }
}

class CompositeIterator extends Iterator {
  constructor(children) {
    super();
    this.children = children;
    this.index = 0;
    this.currentIterator = null;
  }
  hasNext() {
    while (true) {
      if (this.currentIterator === null) {
        if (this.index >= this.children.length) return false;
        this.currentIterator = this.children[this.index].createIterator();
        this.index++;
      }
      if (this.currentIterator.hasNext()) return true;
      else this.currentIterator = null;
    }
  }
  next() {
    if (!this.hasNext()) throw new Error('No more elements');
    return this.currentIterator.next();
  }
}

// Driver code
const root = new Composite('root');
const folder1 = new Composite('Folder1');
folder1.add(new Leaf('FileA'));
folder1.add(new Leaf('FileB'));
const folder2 = new Composite('Folder2');
folder2.add(new Leaf('FileC'));
root.add(folder1);
root.add(folder2);

const iterator = root.createIterator();
while (iterator.hasNext()) {
  const c = iterator.next();
  if (c instanceof Composite) {
    console.log(`Composite: ${c.name}`);
  } else {
    console.log(`Leaf: ${c.name}`);
  }
}

Line Notes

class Component {Base component class with iterator factory method

createIterator() { throw new Error('Not implemented'); }Abstract method to be overridden by subclasses

class LeafIterator extends Iterator {Iterator for leaf nodes yielding itself once

class CompositeIterator extends Iterator {Iterator for composite nodes iterating over children iterators

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node visited once; iterator stack depth bounded by tree height h.

💡 For 1000 nodes with height 10, expect about 1000 operations and stack size up to 10.

Interview Verdict: Accepted

This approach fully embraces polymorphism and encapsulation, making traversal extensible and clean.

📊

All Approaches - One-Glance Tradeoffs

💡 For interviews, approach 2 or 3 are best to code as they show understanding of iterator pattern and abstraction.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(h) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Iterator Pattern Implementation	O(n)	O(h) explicit stack	No	N/A	Good to code - shows design pattern knowledge
3. Composite Pattern with Iterator Interface	O(n)	O(h) iterator stack	No	N/A	Best to code if time permits - shows full abstraction

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and confirm traversal requirements.Step 2: Present the brute force recursive traversal to show understanding.Step 3: Introduce the iterator pattern to separate traversal logic.Step 4: Show the composite pattern with integrated iterators for full abstraction.Step 5: Discuss tradeoffs and answer follow-up questions.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of design patterns, abstraction, separation of concerns, and ability to implement iterators over complex structures.

Common Follow-ups

• How would you implement breadth-first traversal? → Use a queue instead of a stack in the iterator.
• How to support removal of elements during iteration? → Implement remove method in iterator and update composite accordingly.

💡 These follow-ups test your flexibility with traversal order and iterator interface completeness.

🔍

Pattern Recognition

When to Use

1) You have a tree or graph-like structure with composite and leaf nodes. 2) You want to traverse uniformly without exposing internals. 3) You want to separate traversal logic from structure. 4) You want to support multiple traversal strategies.

Signature Phrases

'Provide a uniform way to traverse all elements''Traversal should not expose internal details'

NOT This Pattern When

Simple tree traversal without abstraction or iterator interface is not this pattern.

Similar Problems

Composite Pattern Traversal - similar tree traversal abstractionIterator Pattern Implementation - encapsulating traversal stateTree Traversal with Composite - combining structure and iteration

Practice

1. You have a payment processing system that currently uses multiple if-else statements to handle different payment methods like credit card, UPI, and net banking. The system needs to be extended frequently with new payment methods without modifying existing code. Which design approach best addresses this requirement?

easy

A. Use a brute force approach with nested if-else statements for each payment method.

B. Implement a strategy pattern where each payment method is encapsulated in its own class implementing a common interface.

C. Use a recursive function that selects payment methods based on input parameters.

D. Apply a greedy algorithm to select the payment method with the lowest processing fee.

Solution

1. Step 1: Understand the problem of frequent extension

   The system requires adding new payment methods without modifying existing code, which violates the open-closed principle if using if-else chains.

2. Step 2: Identify the design pattern that encapsulates behaviors

   The strategy pattern encapsulates each payment method in its own class implementing a common interface, allowing easy extension by adding new classes without changing existing code.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Strategy pattern replaces conditionals with polymorphism [OK]

Hint: Replacing conditionals with polymorphism enables easy extension [OK]

Common Mistakes:

• Thinking recursion or greedy algorithms solve extensibility here

2. Which of the following is a common trade-off when using a Facade pattern in a large system?

medium

A. Facade can hide too much complexity, making it hard to access advanced features of subsystems

B. Facade increases coupling between client and subsystems by exposing detailed interfaces

C. Facade always adds significant runtime overhead due to extra method calls

D. Facade requires changing the underlying subsystem interfaces to work properly

Solution

1. Step 1: Recall Facade's purpose

   Facade simplifies complex subsystems by providing a unified interface.

2. Step 2: Analyze trade-offs

   While Facade simplifies usage, it can hide advanced features, limiting flexibility.

3. Step 3: Evaluate other options

   A is incorrect because Facade reduces coupling by hiding subsystem details. C is incorrect; Facade's overhead is minimal. D is wrong; Facade does not require changing subsystems.

4. Final Answer:

   Option A -> Option A

Hint: Facade hides complexity but may hide power

Common Mistakes:

• Believing Facade increases coupling instead of reducing it
• Assuming Facade adds heavy runtime overhead
• Thinking Facade requires modifying subsystems

3. Which of the following is a common trade-off or limitation when favoring composition over inheritance in object-oriented design?

medium

A. Composition always leads to more complex code and harder maintenance than inheritance

B. Composition can increase the number of objects and indirection, potentially impacting performance

C. Composition prevents code reuse since behaviors cannot be shared

D. Composition forces tight coupling between composed objects

Solution

1. Step 1: Evaluate each option's validity

   Composition always leads to more complex code and harder maintenance than inheritance is false; composition often improves maintainability. Composition prevents code reuse since behaviors cannot be shared is false; composition promotes code reuse via behavior objects. Composition forces tight coupling between composed objects is false; composition reduces coupling by separating concerns.

2. Step 2: Understand the trade-off

   Composition introduces more objects and delegation layers, which can add runtime overhead and complexity in object management.

3. Step 3: Confirm correct trade-off

   Composition can increase the number of objects and indirection, potentially impacting performance correctly identifies the potential performance and complexity cost of increased indirection.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Composition trades off some runtime overhead for flexibility and maintainability.

Hint: Composition trades flexibility for some performance overhead, not complexity or coupling.

Common Mistakes:

• Believing composition always simplifies code without cost
• Thinking composition prevents code reuse

4. Which of the following statements about encapsulation in the Snake and Ladder game design is INCORRECT?

medium

A. The Board class hides the details of snakes and ladders from other components, exposing only necessary methods

B. Encapsulation ensures that the Player's position can only be changed through controlled methods, preventing invalid moves

C. The Dice class should expose its internal random number generator to allow external manipulation for testing

D. GameController encapsulates the game rules and state transitions, preventing inconsistent game states

Solution

1. Step 1: Encapsulation of Player position

   Correct: Position changes only via controlled methods to maintain validity.

2. Step 2: Dice class design

   Incorrect: Exposing internal RNG breaks encapsulation and risks inconsistent behavior.

3. Step 3: Board class encapsulation

   Correct: Board hides snake/ladder details, exposing only necessary interfaces.

4. Step 4: GameController encapsulation

   Correct: It manages rules and state transitions to keep game consistent.

5. Final Answer:

   Option C -> Option C

6. Quick Check:

   Only Dice exposing internal RNG violates encapsulation principles.

Hint: Encapsulation means hiding internals, not exposing them for convenience [OK]

Common Mistakes:

• Thinking exposing RNG aids testing without drawbacks
• Confusing encapsulation with just data hiding
• Assuming all classes should expose internals for flexibility

5. What is a key trade-off or limitation when using multiple inheritance to solve the Diamond Problem in object-oriented design?

medium

A. Multiple inheritance always leads to ambiguous method calls that cannot be resolved.

B. Multiple inheritance eliminates the need for Method Resolution Order (MRO).

C. Multiple inheritance reduces code reuse compared to single inheritance.

D. Using multiple inheritance can increase complexity and make the class hierarchy harder to understand and maintain.

Solution

1. Step 1: Understand the Diamond Problem

   Diamond Problem arises when a class inherits from two classes that share a common ancestor, causing ambiguity.

2. Step 2: Evaluate Multiple inheritance always leads to ambiguous method calls that cannot be resolved.

   Multiple inheritance can cause ambiguity, but languages use MRO to resolve it, so it is not always unresolved.

3. Step 3: Evaluate Multiple inheritance eliminates the need for Method Resolution Order (MRO).

   MRO is essential in multiple inheritance to resolve method calls, so multiple inheritance does not eliminate MRO.

4. Step 4: Evaluate Multiple inheritance reduces code reuse compared to single inheritance.

   Multiple inheritance generally increases code reuse by combining features from multiple classes.

5. Step 5: Correct trade-off

   Using multiple inheritance can increase complexity and make the class hierarchy harder to understand and maintain. correctly identifies that multiple inheritance increases complexity and can make hierarchies harder to maintain.

6. Final Answer:

   Option D -> Option D

7. Quick Check:

   Complexity and maintainability are key trade-offs in multiple inheritance.

Hint: Multiple inheritance = power with complexity cost

Common Mistakes:

• Believing multiple inheritance always causes irresolvable ambiguity
• Thinking MRO is unnecessary with multiple inheritance
• Assuming multiple inheritance reduces code reuse