Back to course home
0% completed
Vote For New Content
For the Space Complexity of the non-multi-threaded solution, why does the stack ...
Mike Xu
Feb 10, 2023
For the Space Complexity of the non-multi-threaded solution, why does the stack take O(N) space but to store nodes we need O(H)? O(N) and O(H) should be the same, right?
0
0
Comments
Comments
S
sevillaarvin 8 months ago
No. Given this tree:
1 / \ 2 3 / \ / \ 4 5 6 7
Depth first search will reach the leaf node first, so the stack looks like this:
1 / 2 / 4
It will back track and do a dive on the next node:
1 ...
On this page