0

What is the time complexity of traversing all nodes in a tree using the Composite Pattern iterator, where n is the total number of nodes and h is the height of the tree?

medium🪤 Complexity Trap Q5 of Q15

OOP & Design Patterns - Iterator & Composite Pattern - Traversal Abstractions

What is the time complexity of traversing all nodes in a tree using the Composite Pattern iterator, where n is the total number of nodes and h is the height of the tree?

AO(n^2) due to nested iteration over children

BO(h) because traversal depends on tree height

CO(n * h) because each node may be revisited up to height times

DO(n) because each node is visited exactly once

Step-by-Step Solution

Solution:

Step 1: Analyze traversal behavior
Composite iterator visits each node once during traversal.
Step 2: Determine complexity
Visiting n nodes once yields O(n) time complexity.
Final Answer:
Option D -> Option D
Quick Check:
Each node visited once -> O(n) time [OK]

Quick Trick: Traversal visits each node once -> O(n) time [OK]

Common Mistakes:

MISTAKES

Confusing height with traversal cost
Assuming repeated visits increase complexity
Thinking nested loops cause O(n^2)

Trap Explanation:

PITFALL

Candidates often confuse tree height with traversal time or assume repeated visits.

Interviewer Note:

CONTEXT

Tests understanding of traversal time complexity in composite iterators.

Master "Iterator & Composite Pattern - Traversal Abstractions" in OOP & Design Patterns

2 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More OOP & Design Patterns Quizzes