DFS an BFS for Tree

less than 1 minute read

Memory Complexity

For a tree like structure, for the purpose of understanding

For a balanced tree with n nodes, there will n/2 leaf nodes due to which the memory complexity of BFS will on O(n)

For DFS, the max memory will the height of the tree which in logN, and that is why the memory complexity is O(logN)

You may also enjoy