3 ms·
The article claims that the space requirement for depth-first search of a binary tree is O(log N). This is incomplete for the broader category of binary trees.
by loeg 10y ago
The article claims that the space requirement for depth-first search of a binary tree is O(log N). This is incomplete for the broader category of binary trees.
The space requirement for depth-first search of a non-balanced binary tree is pretty clearly O(N), not O(log N). (Consider the "linked list" tree.)
For balanced trees, O(log N) is correct. This is because space required for depth-first search is identical to maximum tree depth. And balanced trees bound depth at O(log N), while non-balanced trees can be O(N) deep.
While the article leaves out the mention of the term balanced, the described "perfect" trees happen to be balanced.
- eeojun 10y agoHi, original author here. I used "perfect" trees as I wanted to generalise it to trees of other "types", not just binary trees. But yes, you are correct that it is incomplete for the broader category of binary trees.
- loeg 10y agoOther types of trees can also be unbalanced :-). E.g., the classic example of DFS is maze-solving, which is usually unbalanced.