What is the time complexity of tree traversal?

tree time-complexity tree-traversal
new299 picture new299 · Feb 10, 2011 · Viewed 35.3k times · Source

What is the time complexity of tree traversal, I'm sure it must be obvious but my poor brain can not work it out right now.

Answer

Uri picture Uri · Feb 10, 2011

It depends what kind of traversal you are performing and the algorithm, but typically it would be O(n) where n is the total number of nodes in the tree. The canonical recursive implementation of depth first traversal, will consume memory (on the stack) in the order of the deepest level, which on a balanced tree it would be log(n).

Related questions

Worst case in Max-Heapify - How do you get 2n/3?

In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY, The children’s subtrees each have size at most 2n/3—the worst case occurs when the bottom level of the tree is exactly half full. I understand why …

Read More
How to implement a tree data-structure in Java?

Is there any standard Java library class to represent a tree in Java? Specifically I need to represent the following: The sub-tree at any node can have an arbitrary number of children Each node (after the root) and it's children …

Read More
How can I implement a tree in Python?

I am trying to construct a General tree. Are there any built-in data structures in Python to implement it?

Read More