Printing a binary tree in BFS mode using O (1) space

Question

I was wondering if it is possible to print a binary tree in first order when using only O (1) space?

The hard part is that you need to use extra space to remember the next level to go through, and this grows with n.

Since we are not limiting the time part, maybe there are some ineffective (in terms of time) ways that can achieve this?

Any idea?

Answer 1

This will depend on some more subtle definitions, for example, if the edges have backlinks. Then it's easy, because you can just follow the tree feedback. Otherwise, I can’t think of a way to do this without O (lg number of nodes) space, because you need to remember at least the nodes “above”.

Update

Oh wait, of course, this can be done in O (1) space by trading space time. Wherever you would like to make feedback, you save your place and execute BFS by tracking the very last node until you find yours. Then go back to the last node visited and continue.

The problem is that O (1) is space, but O (n ^ 2) is time.

Another update

Suppose we reach node n_i and we want to reach the parent element node, which we will call wlg n_j. We have identified the outstanding root node n_0.

Modify the first breath search algorithm so that when it follows the directional edge (n_x, n_y), the efferent or “incoming” node is saved. That way, when you follow (n_x, n_y), you save n_x.

When you start BFS again from n_0, you are guaranteed (suppose it is really a tree) that at a SOME point you will go to the edge (n_j, n_i). At this point, you are observing that you are back at n_i. You saved n_j, and you know that the reverse edge (n_i, n_j).

Thus, you get this single rollback with two additional cells, one for n_0 and one for the "saved" node. This is O (1)

I am not sure about O (n ^ 2) - it was late, and it was a difficult day, so I do not want to make evidence. I am sure that O ((| N | + | E |) ^ 2), where | N | and | E | - the size of the sets of vertices and edges, respectively.

Answer 2

I know that this is strictly not the answer to the question, but visiting the tree nodes in width order can be done using the O (d) space, where d is the depth of the tree, recursive iterative deepening of the first search depth (IDDFS). Of course, stack space is required. In the case of a balanced tree, d = O (log n), where n is the number of nodes. I honestly don't understand how you will do this in a constant space without the backlinks suggested by @Charlie Martin.

Answer 3

An interesting special case is heaps.

From heapq docs :

Heaps are binary trees for which each parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. For comparison, nonexistent elements are considered infinite. An interesting property of the heap is that its smallest element is always the root, heap[0] . [explanation of Francois Pinard]

Like a tree represented in memory (array indices):

  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 

In this case, the nodes in the array are already stored in first order.

 for value in the_heap: print(value) 

O (1) in space.