NPTEL Assignment Question

Question

What is the complexity of inorder traversal for a binary search tree with n nodes? 

• A. O(log n) whether the tree is balanced or unbalanced.
• B. O(log n) if the tree is balanced, O(n) otherwise.
• C. O(n) whether the tree is balanced or unbalanced.
• D. O(n) if the tree is balanced, O(n log n) otherwise.

Answer 1

The correct answer is C, O(n) whether the tree is balanced or unbalanced.

The logical reasoning behind in inorder traversal is that for each node you

1. traverse the left sub-tree of the current node
2. print/traverse the current node and
3. traverse the right sub-tree of the current node.

In any case, balanced or unbalanced you essentially only visit all the nodes once. Since you are visiting all the nodes the time complexity will be equal to the number of nodes, i.e. n.

 

Additional context: In the case of search in a binary search tree time taken to search a node would be O(log n) if the tree is balanced, O(n) otherwise. 

Comments

Upvote