The runtime for traversing all the nodes of a binary search tree with n nodes…
2016
The runtime for traversing all the nodes of a binary search tree with n nodes and printing them in an order is
- A.
\(O(lg \ n) \) - B.
\(O(n \ lg \ n) \) - C.
\(O(n)\) - D.
\(O(n^2)\)
Attempted by 489 students.
Show answer & explanation
Correct answer: C
Answer: O(n). A full traversal visits each node exactly once and printing each node takes constant time.
Key idea: Use an in-order, pre-order, or post-order traversal — each visits all n nodes one time.
Work per node: O(1) for printing or processing the node.
Total time: n × O(1) = O(n).
Note: Searching for a single element in a balanced BST is O(log n), which is different from traversing and printing all nodes.