CODEWITHSUNDEEP
treetime-complexitytraversalinorder
2950_Rutuja Wasu
2950_Rutuja Wasu

Reputation: 11

why is time complexity of tree traversal O(n)

why is time complexity in inorder , preorder and postorder traversal of a tree O(n)? What is it for AVL tree? As avl tree is balanced does time complexity change as compared to bst?

Upvotes: 1

Views: 2483

Answers (1)

trincot
trincot

Reputation: 350127

The time complexity for inorder, preorder and postorder traversal of a tree is O(𝑛) because these traversals visit a node at most twice: when encountering it while going down an edge, and while going back up along that same edge. Travelling along an edge in either direction has a cost that does not depend on 𝑛... it is O(1), and so the overall time complexity is O(𝑛).

It does not matter whether the binary tree is well balanced or not at all, because the number of edges remains the same: it is always one less than the number of nodes.

It certainly does not matter whether the binary tree is a binary search tree or not: this only puts conditions on the values in the nodes, and they don't matter at all for these types of traversals.

Upvotes: 2

Related Questions