Difference between finding Inorder Successor vs finding next using Inorder Traversal in BST

Question

How is it possible that the time complexity of inorder traversal is O(n), because the time complexity of Inorder Successor in Binary Search Tree is O(log n), So the inorder traversal in BST for printing the numbers take O(n*logn) time for 'n' nodes???

Comments

Time Complexity of finding inorder successor in binary search tree  is O(h) where h represents the height which is in turn O(n) so the time complexity of finding inorder successor in a binary search tree is O(n) but it is O(log n) in balanced binary search tree.

Answer 1

1.How is it possible that the time complexity of inorder traversal is O(n),

as in inorder traversal we have to start from left and got to middlae and right so each and everry element is processed so o(n).

2.because the time complexity of Inorder Successor in Binary Search Tree is O(log n),

the time complexity of inorder successor in binary search tree is O(logn) as 2^H-1=n

so h=logn

3.So the inorder traversal in BST for printing the numbers take O(n*logn) time for 'n' nodes???

so as u printing the numbers then u have to access each and every elements O(n) at height O(logn)

and they are execute in combined so O(logn)

hope it will help