What is the time and space complexity of a breadth first and depth first tree traversal?
AlgorithmAlgorithm Problem Overview
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?
Algorithm Solutions
Solution 1 - Algorithm
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.
Solution 2 - Algorithm
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.
Solution 3 - Algorithm
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)