Space Requirements for Tree Traversal | Hacker News Reader

Space Requirements for Tree Traversal

eugene-eeo.github.io

73 pointswq20 comments

I believe "Iterative deepening depth-first search" should be mentioned since the result is equivalent to breadth-first search but the memory efficiency is basically the same as depth-first search. It also tends to be faster than breadth-first search due to the lower memory complexity.

https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs...

I came here to say this :)

Oh boy, this is great. Thanks! I was not aware of this when I wrote the article/post. I started out by wanting to make a very generalised pair of expressions for the space requirements so I had to make very little assumptions and would be able compare it to efficiency gains by other algorithms/representations.

Again thanks, I'll try to include it this week end if I have the time.

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.

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.

Other types of trees can also be unbalanced :-). E.g., the classic example of DFS is maze-solving, which is usually unbalanced.

> iteratively using LIFO queues or FIFO stacks.

Aren't queues FIFO and stacks LIFO? Or am I just confused and there is some FIFO stack thing I haven't heard of yet?

It does seem like the author swapped those two.

Whoops, you're right. I've fixed it. Thanks for pointing it out!

If you want O(1) space complexity and you do not care about modifying the tree, you can do tree rotations essentially flattening out the tree into a singly linked list.

Are you assuming that nodes have parent pointers?

You don't need parent pointers.

For converting binary tree into a linked list in O(n) time and O(1) space.

You have two pointers, the root and the tail (right child node).

If root has a left subtree, set tail->right = left subtree. Update tail again so it is the last right child node.

root = root->right

Repeat until root is NULL

Thanks!

One does not need to flatten tree if tree modifications are allowed. Just use Deutsch-Schorr-Waite algorithm.

Hi, original author here. I did not expect so much discussion and awareness! Once again I have to stress that I wanted to make a very general pair of equations so I could compare the efficiency gains in other algorithms from the naive versions in an 'accurate' way. If anyone has any suggestions for the algorithms involved please let me know (141bytes@gmail.com) and I'll see if it's suitable to put in. I apologise in advance if I take longer than usual to reply, A levels are a ton of work!

Also I was originally going to see how this applied to traversing really large, cross machine trees so I did not consider the algorithms that mutated the tree, but thanks for making me aware of those.

For Red-Black tree (balanced tree) preorder/inorder/postorder traversal, which involves depth first scan, 2 * log(n) additional space is required ([1]).

[1] Here is an example, look for st_tr_aux() function: https://github.com/faragon/libsrt/blob/master/src/stree.c

If the nodes have parent pointers, which does tend to be somewhat common, then depth-first can be done in constant space. I haven't implemented it before, but I believe breadth-first should also take constant space in this case.

If the nodes have parent pointers, everything is paying extra O(n) space.

Space is already O(n)

Related: Morris Traversal (no parent link required).

https://en.wikipedia.org/wiki/Tree_traversal#Morris_in-order...

Trying to reimplement it without looking at the solution is fun.

Reply on news.ycombinator.com