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. When a client calls a method on a Proxy object that controls access to a resource-intensive service, what is the typical sequence of events that occurs internally?

easy

A. Proxy performs access control, then lazily initializes the real service if needed, and finally forwards the call

B. Proxy immediately forwards the call to the real service without any checks

C. Proxy modifies the request parameters before forwarding to the real service

D. Proxy creates a simplified interface hiding the complexity of the real service

Solution

1. Step 1: Understand Proxy's role

   Proxy controls access and may delay creation of the real service (lazy initialization).

2. Step 2: Trace the call flow

   Client calls Proxy -> Proxy checks access -> Proxy creates real service if not already created -> Proxy forwards call -> Real service executes.

3. Step 3: Eliminate incorrect options

   B is incorrect because Proxy usually adds control logic before forwarding. C is incorrect as Proxy typically does not modify parameters (that's Decorator or Adapter). D describes Facade, not Proxy.

4. Final Answer:

   Option A -> Option A

Hint: Proxy = gatekeeper + lazy loader

Common Mistakes:

• Assuming Proxy always forwards calls immediately without checks
• Confusing Proxy with Facade's simplification role
• Thinking Proxy modifies request parameters

2. In the object-oriented design of a Snake and Ladder game, which component is primarily responsible for managing the state transitions of a player's position after a dice roll?

easy

A. The Dice class, since it generates the number that determines movement

B. The Player class, as it holds the current position and updates it directly

C. The Board class, because it contains the snakes and ladders and applies their effects

D. The GameController class, which orchestrates the game flow and updates player positions accordingly

Solution

1. Step 1: Understand the role of Dice

   The Dice only generates a random number; it does not manage state transitions.

2. Step 2: Consider Player class responsibilities

   Player holds position but should not decide how to update it considering snakes or ladders.

3. Step 3: Analyze Board class role

   Board knows snakes and ladders but does not manage player state transitions directly.

4. Step 4: Role of GameController

   GameController coordinates dice roll, queries Board for snakes/ladders, and updates Player position accordingly.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   GameController centralizes state transitions, ensuring separation of concerns.

Hint: GameController orchestrates state changes, not Dice or Player alone [OK]

Common Mistakes:

• Thinking Dice manages player position
• Assuming Player updates position without Board's input
• Believing Board directly changes player state

3. In which scenario is applying the Liskov Substitution Principle (LSP) most critical to ensure system correctness?

easy

A. When a subclass adds new methods without overriding any superclass methods.

B. When a subclass uses composition instead of inheritance.

C. When a subclass narrows the input parameter types of an overridden method.

D. When a subclass extends a superclass but changes the expected behavior of inherited methods.

Solution

1. Step 1: Understand LSP's core requirement

   LSP requires that subclasses can replace their superclasses without altering desirable properties of the program, especially behavior.

2. Step 2: Analyze each option carefully

   When a subclass extends a superclass but changes the expected behavior of inherited methods. describes a subclass changing expected behavior, which violates LSP. When a subclass adds new methods without overriding any superclass methods. is safe as adding methods doesn't break substitutability. When a subclass narrows the input parameter types of an overridden method. narrows input types (contravariance violation), which breaks substitutability but is less direct than changing behavior. When a subclass uses composition instead of inheritance. is unrelated to LSP since composition is an alternative to inheritance.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only changing inherited method behavior breaks LSP directly.

Hint: LSP is about preserving inherited behavior, not just adding features.

Common Mistakes:

• Thinking adding methods breaks LSP
• Confusing covariance and contravariance in parameters
• Assuming composition relates directly to LSP

4. Imagine a class responsible for both data persistence and data validation. When a change in validation rules occurs, trace the impact on the class and explain what happens step-by-step.

easy

A. Only the validation methods need modification; persistence remains unaffected, so SRP is maintained.

B. Changing validation rules forces modifying the entire class, risking unintended side effects on persistence logic.

C. Validation changes automatically propagate to persistence without code changes due to tight coupling.

D. Persistence logic will break because validation and persistence are tightly integrated and inseparable.

Solution

1. Step 1: Identify responsibilities

   The class handles both validation and persistence, two distinct reasons to change.

2. Step 2: Trace change impact

   Changing validation rules requires modifying validation code inside the class.

3. Step 3: Side effects

   Because persistence logic shares the class, changes risk affecting persistence unintentionally, increasing maintenance risk.

4. Step 4: SRP violation

   This coupling violates SRP, as one reason to change (validation) affects unrelated functionality (persistence).

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   One reason to change should not force changes in unrelated code -> SRP violation.

Hint: One reason to change means one place to modify.

Common Mistakes:

• Assuming changes affect only related methods without side effects.
• Believing tight coupling is harmless if code is in one class.
• Thinking validation and persistence are always linked.

5. Identify the bug in the following Python code implementing deep copy for the Profile class:

import copy

class Profile:
    def __init__(self, name, scores):
        self.name = name
        self.scores = scores

    def __deepcopy__(self, memo):
        new_name = self.name  # Bug here
        new_scores = copy.deepcopy(self.scores, memo)
        return Profile(new_name, new_scores)

original = Profile('Alice', [10, 20])
copy_obj = copy.deepcopy(original)
copy_obj.scores.append(30)
print(original.scores)

medium

A. Line assigning new_name = self.name does not deepcopy the name string

B. Line assigning new_scores = copy.deepcopy(self.scores, memo) incorrectly copies scores

C. The __init__ method does not initialize scores properly

D. The return statement returns a new Profile instead of modifying self

Solution

1. Step 1: Examine __deepcopy__ method

   The line new_name = self.name copies the reference to the name string instead of deep copying it.

2. Step 2: Understand impact

   Strings are immutable in Python, so shallow copy is usually safe, but if name were a mutable object, this would cause shared references and bugs. Proper deep copy should be used for consistency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only new_name assignment lacks deepcopy -> subtle bug [OK]

Hint: All nested fields must be deep copied consistently [OK]

Common Mistakes:

• Forgetting to deepcopy all nested fields, assuming immutables are safe