21

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.

RK-
  • 12,099
  • 23
  • 89
  • 155
new299
  • 804
  • 1
  • 7
  • 17

2 Answers2

25

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).

Uri London
  • 10,631
  • 5
  • 51
  • 81
  • Is this true of an n-ary tree? I have a data structure that is a tree of max-depth 4 and to traverse it my friend is using 3 for loops, and is saying his algorithm runs in `O(n^3)` time, but I believe it's running in `n` time, `n` being to total number of nodes in the tree – Nicholas Nov 08 '12 at 00:58
  • 4
    @Nocholas, you are correct and your friend is wrong. It is O(n). – Uri London Nov 08 '12 at 07:05
2

Wouldn't that just be n for a tree with n nodes?

You visit each tree-leave once, don't you? So i'd say it is linear.

Nanne
  • 64,065
  • 16
  • 119
  • 163
  • I guess it should be tree with "n nodes" and not "n leaves". – aamadmi Jul 22 '13 at 11:31
  • @Nanne With the right algorithm it's indeed a linear complexity in time (visiting each node once), but it might still not have a linear complexity in space. Like using the stack. – Tim Aug 25 '15 at 20:02
  • But the question was about time complexity. – Nanne Aug 26 '15 at 06:35