101

Can someone explain with an example how we can calculate the time and space complexity of both these traversal methods?

Also, how does recursive solution to depth first traversal affect the time and space complexity?

3

3 Answers 3

137

BFS:

Time complexity is O(|V|), where |V| is the number of nodes. You need to traverse all nodes.
Space complexity is O(|V|) as well - since at worst case you need to hold all vertices in the queue.

DFS:

Time complexity is again O(|V|), you need to traverse all nodes.
Space complexity - depends on the implementation, a recursive implementation can have a O(h) space complexity [worst case], where h is the maximal depth of your tree.
Using an iterative solution with a stack is actually the same as BFS, just using a stack instead of a queue - so you get both O(|V|) time and space complexity.

(*) Note that the space complexity and time complexity is a bit different for a tree than for a general graphs becase you do not need to maintain a visited set for a tree, and |E| = O(|V|), so the |E| factor is actually redundant.

9
  • 6
    @500_error For a tree, you don't need a visited set - because there is a single path from the root to each node. The purpose of the visited set is to avoid re-expanding same node multiple times, but since there is a single path - that cannot happen (in directed graphs - no need for any more data, in undirected graphs, need to remember the parent of each node in the front and that's it)
    – amit
    Jul 29, 2015 at 21:35
  • 3
    I'm not sure if this answer is right? It says the space complexity of DFS is O(|V|) using a stack. However, the stack implementation only uses O(bd) space where b is the branching factor and d is the depth. However, bd != V. On the other hand, b^d = V. Thus, I think the space complexity can be bounded more tightly by O(bd) rather than saying O(|V|).
    – nave
    Sep 8, 2015 at 0:32
  • 1
    @nave Under worst case, this is O(|V|), since assume you have one branch of length |V|/2, you will have to hold all these |V|/2 nodes in the stack. Note that the answer says it's worst case behavior.
    – amit
    Sep 8, 2015 at 6:09
  • 1
    @amit - in an iterative implementation, a node is popped from the stack or queue for DFS and BFS respectively as it is visited. So why is space complexity ever O(N)? The unvisited stack or queue will never contain all nodes. Where am I going wrong?
    – Jack
    Apr 1, 2016 at 17:17
  • 2
    @MariaInesParnisari because the question is about a tree. There are n-1 edges in a tree, so the traversing all edges and all vertices is the same as traversing all vertices. (Note that the answer explicitly explains this).
    – amit
    Apr 19, 2020 at 5:29
47

DFS and BFS time complexity: O(n)

Because this is tree traversal, we must touch every node, making this O(n) where n is the number of nodes in the tree.

BFS space complexity: O(n)

BFS will have to store at least an entire level of the tree in the queue (sample queue implementation). With a perfect fully balanced binary tree, this would be (n/2 + 1) nodes (the very last level). Best Case (in this context), the tree is severely unbalanced and contains only 1 element at each level and the space complexity is O(1). Worst Case would be storing (n - 1) nodes with a fairly useless N-ary tree where all but the root node are located at the second level.

DFS space complexity: O(d)

Regardless of the implementation (recursive or iterative), the stack (implicit or explicit) will contain d nodes, where d is the maximum depth of the tree. With a balanced tree, this would be (log n) nodes. Worst Case for DFS will be the best case for BFS, and the Best Case for DFS will be the worst case for BFS.

6
  • 11
    It should be O(V+E), you need to consider the edges as well.
    – Kyle
    May 27, 2019 at 14:22
  • 6
    @Kyle, in case of a normal graph you are right. In case of a binary tree its O(N) because the number of edges is constant
    – Jiloc
    Jul 11, 2020 at 13:58
  • 6
    If you're looking for trees, this is the best answer.
    – SDG
    Aug 30, 2020 at 5:30
  • 4
    All trees (binary or not) have n-1 edges. O(n + (n-1)) = O(n) Sep 21, 2020 at 23:06
  • Are you sure DFS space complexity is O(d) for non-binary trees? Mar 25 at 23:43
7

There are two major factors of complexity

  1. Time Complexity
  2. Space complexity

Time Complexity

It is the amount of time need to generate the node.

In DFS the amount of time needed is proportional to the depth and branching factor. For DFS the total amount of time needed is given by-

1 + b + b2 + b3 + ... + bd ~~ bd

Thus the time complexity = O(bd)


Space complexity

It is the amount of space or memory required for getting a solution DFS stores only current path it is pursuing. Hence the space complexity is a linear function of the depth.

So space complexity is given by O(d)

3
  • Well this doesn't apply to tree traversal, which is a kind of a special case. So this answer can be misleading.
    – xji
    Feb 4, 2017 at 20:40
  • It should be O(h). As d referring to depth is relative to a node.
    – Fawkes
    Nov 19, 2021 at 7:47
  • For graph traversal, it would be O(V+E). Worst-case O(n^2) when graph is dense i.e. all nodes are connected with each other.
    – Fawkes
    Nov 19, 2021 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.