Print binary tree in BFS fashion with O(1) space

Question

I was wondering if it's possible to print a binary tree in breadth first order while using only O(1) space?

The difficult part is that one have to use additional space to memorize the next level to traverse, and that grows with n.

Since we haven't place any limitation on the time part, maybe there are some inefficient (in terms of time) ways that can achieve this?

Any idea?

Answer 1

This is going to depend on some finer-grained definitions, for example if the edges have back-links. Then it's easy, because you can just follow a back link up the tree. Otherwise I can't think off hand of a way to do it without O(lg number of nodes) space, because you need to remember at least the nodes "above".

Update

Oh wait, of course it can be done in O(1) space with a space time trade. Everywhere you would want to do a back link, you save your place and do BFS, tracking the most recent node, until you find yours. Then back up to the most recently visited node and proceed.

Problem is, that's O(1) space but O(n^2) time.

Another update

Let's assume that we've reached node n_i, and we want to reach the parent of that node, which we'll call wlg n_j. We have identified the distinguished root node n_0.

Modify the breath-first search algorithm so that when it follows a directed edge (n_x,n_y), the efferent or "incoming" node is stored. Thus when you follow (n_x,n_y), you save n_x.

When you start the BFS again from n_0, you are guaranteed (assuming it really is a tree) that at SOME point, you will transition the edge (n_j,n_i). At that point you observe you're back at n_i. You've stored n_j and so you know the reverse edge is (n_i,n_j).

Thus, you get that single backtrack with only two extra cells, one for n_0 and one for the "saved" node. This is O(1)

I'm not so sure of O(n^2) -- it's late and it's been a hard day so I don't want to compose a proof. I'm sure it's O((|N|+|E|)^2) where |N| and |E| are the size of the sets of vertices and edges respectively.

Answer 2

An interesting special case is heaps.

From heapq docs:

Heaps are binary trees for which every 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 the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, heap[0]. [explanation by François Pinard]

How a tree represented in memory (indexes of the array):

                               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 nodes in the array are already stored in a breadth first order.

for value in the_heap:
    print(value)

O(1) in space.

Answer 3

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

Answer 4

It is easy to implement a recursive method to get all the nodes of a tree at a given level. Hence, we could calculate the height of the tree and get all the nodes and each level. This is Level Order Traversal of the tree. But, the time complexity is O(n^2). Below is the Java implementation (source).

class Node 
{ 
    int data; 
    Node left, right; 
    public Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 

class BinaryTree 
{ 
    Node root; 

    public BinaryTree() 
    { 
        root = null; 
    } 

    void PrintLevelOrder() 
    { 
        int h = height(root); 
        int i; 
        for (i=1; i<=h; i++) 
            printGivenLevel(root, i); 
    } 

    int Height(Node root) 
    { 
        if (root == null) 
           return 0; 
        else
        { 
            int lheight = height(root.left); 
            int rheight = height(root.right); 

        } 
    } 

    void PrintGivenLevel (Node root ,int level) 
    { 
        if (root == null) 
            return; 
        if (level == 1) 
            System.out.print(root.data + " "); 
        else if (level > 1) 
        { 
            printGivenLevel(root.left, level-1); 
            printGivenLevel(root.right, level-1); 
        } 
    }
}