Re:Space Requirements for Tree Traversal
by loeg on Sunday October 09, 2016 @04:44PM
(#12673367)
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.
Re:Space Requirements for Tree Traversal
by eeojun on Monday October 10, 2016 @08:49AM
(#12676735)
Hi, 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.
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.