Relatively new to algorithms, so please forgive if I've missed something obvious!
I know that the space-complexity of depth-first search is commonly expressed as O(h), where h is the height of the tree, whereas breadth-first search's complexity is O(n), where n is the number of nodes in the tree.
I understand the explanation (such as in this answer https://stackoverflow.com/a/9844323/10083571) that, in the worst case within BFS, all the nodes are on one level, meaning we have to queue all the nodes up before traversing them. I also understand that the space complexity of a tree will be determined by its height, as this will determine the maximum layers on the stack that will need to be stored up.
The thing I don't understand, is why this is not also expressed as O(n). Along similar reasoning to the BFS worst case, isn't the DFS worst case that all the nodes are beneath one another, along a single lineage? So in the worst case, the height of a tree will equal the number of nodes it has. So why is this not expressed as O(n) as well?
Thanks
