UGC NET CSE | August 2016 | Part 2 | Question: 23

Question

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})$

Comments

O(n), since we need to  visit all of them , anyway.

Answer 1

Printing the elements in an order means the elements should be printed in sorted order and we know inorder traversal of BST takes gives the sorted order and takes O(n) time.The recurrence involved is :

T(n) = 2T(n/2) + c for balanced BST which on solving gives O(n) and also for skewed tree T(n) = T(n-1) + c which also on solving gives O(n) time.Hence C) is the correct option.