What is the time and space complexity of a breadth first and depth first tree traversal?

Question

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?

There are quite decent explanations available on wikipedia: http://en.wikipedia.org/wiki/Depth-first_search http://en.wikipedia.org/wiki/Breadth-first_search — hc_, Mar 23 '12 at 17:58
@hc_: The wikipedia article talks about general graphs, where DFS has to maintain `visited` set. This is not necessery for trees. — amit, Mar 23 '12 at 18:09
good ref to the question: https://towardsdatascience.com/a-data-scientists-guide-to-data-structures-algorithms-part-2-6bc27066f3fe — David Peer, Apr 28 '21 at 06:04

score 137 · Accepted Answer · edited Jul 25 '20 at 06:26

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.

edited Jul 25 '20 at 06:26

Community

1
1

answered Mar 23 '12 at 18:04

amit

175,853
27
231
333

"you do not need to maintain a visited set for a tree" I thought in BFS you need to maintain a visited set, can you provide a reference. – aarti Jul 29 '15 at 18:43
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 '15 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 08 '15 at 00: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 08 '15 at 06: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 01 '16 at 17:17
1

@Jack In the worst case it'll contain N-1 which is O(N). For the queue, imagine the root has all other nodes as its children, for the stack, imagine a linked list. – keyser Aug 21 '16 at 08:43
1

How is this answer correct? Time complexity is `O(V+E)` since you need to traverse all vertices _and_ edges – Maria Ines Parnisari Apr 17 '20 at 20:29
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 '20 at 05:29
@amit I don't understand. You mean if root has a left and right child, its left child has only left children, its right child has only right children, and `|V|/2` of the nodes are on the right side? Wouldn't the stack: pop the root, push both children. Pop the right side, push one child. Pop that child, push its child. Etc. The stack only has 2 nodes in it at one time, not `|V|/2` nodes – theonlygusti Mar 25 '23 at 23:42

score 46 · Answer 2 · answered Mar 31 '18 at 15:26

46

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.

answered Mar 31 '18 at 15:26

Luke Heytens

469
4
4

11

It should be O(V+E), you need to consider the edges as well. – Kyle May 27 '19 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 '20 at 13:58
6

If you're looking for trees, this is the best answer. – SDG Aug 30 '20 at 05:30
4

All trees (binary or not) have n-1 edges. O(n + (n-1)) = O(n) – Luke Heytens Sep 21 '20 at 23:06
Are you sure DFS space complexity is O(d) for non-binary trees? – theonlygusti Mar 25 '23 at 23:43
This should be the correct answer. The question specifically ask about tree. – Jyhonn Jul 28 '23 at 14:50

score 7 · Answer 3 · edited Jan 22 '17 at 16:41

7

There are two major factors of complexity

Time Complexity
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)

edited Jan 22 '17 at 16:41

nbro

15,395
32
113
196

answered May 15 '14 at 10:02

sumayla khan

97
1
1

Well this doesn't apply to tree traversal, which is a kind of a special case. So this answer can be misleading. – xji Feb 04 '17 at 20:40
It should be O(h). As d referring to depth is relative to a node. – Fawkes Nov 19 '21 at 07: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 '21 at 07:49