The run time for traversing all the nodes of a binary search tree with n nodes and printing them in an order is :

Explanation

Printing the elements in order means printing them in sorted order; inorder traversal of a BST gives the sorted order and visits each node once, taking O(n) time. For a balanced BST T(n) = 2T(n/2) + c and for a skewed tree T(n) = T(n – 1) + c; both solve to O(n).