level order tree traversal without using additional memory

Question

I know about algorithm to level order traversal of a tree. (I think everybody knows about that) That algorithm uses queue to store the nodes of the tree. Is there a algorithm that do not uses additional memory? That algorithm must not use recursion (in that way we are using stack). Note, that tree is given in left-child right-sibling representation. No additional pointers are allowed.
The structures in C, for the tree are:

struct node {
int data;
struct node *left-child;
struct node *right-sibling;
}

Tree is represented with a pointer to the root node. Of course, root cannot have right-sibling.

Answer 1

One way could be to use the right-sibling pointers which are null, to make all nodes siblings of each other (temporarily).

You could use a slow and fast pointer. The fast one would always be at the last sibling (that has a null pointer as right-sibling). The left-child pointer of the slow node would then be copied into that right-sibling, after which the fast pointer runs further to the end again. The slow pointer goes one step to the right and the same repeats. When the slow pointer also reaches the end, all nodes will be siblings. Either the slow or fast pointer can be used to output the values in the level-order. This will do the job, but the tree will have been destroyed as a consequence.

To restore the tree, I would suggest that during the above process the direction of all sibling edges is reversed. This means you need to have another pointer that lags behind the slow pointer. This will allow the reversal to be performed between those two. This is a bit obscure, because the right-sibling will then in fact point to something that is mostly a left sibling.

After the above process, the pointers will be at the end of the node list, but because we have reversed the sibling edges, we can also walk back and reverse the edges again. One difficulty is to know which sibling pointers should become null again (for when a node was originally a right most child). This can be done by having again a fast pointer moving ahead (in the left direction) to find nodes that have child. If the pointer that lags behind the slow pointer hits such a child, we know that the slow pointer's node should get a null pointer as right-sibling. When this fix is applied, the fast pointer should again run ahead to find yet another parent node, ...etc.

Note that the left-child pointers are not altered by this algorithm.

So, in total this solution uses three pointers and the structure of the tree itself.

Here is a sample tree I have used in an implementation below:

          1
         /
        2 ------------ 3 ---------4
       /              /          /
      5 -- 6 -- 7    8 -- 9     10 -- 11 -- 12 -- 13
          /                           /
        14 -- 15 -- 16              17 -- 18 -- 19

Implementation in JavaScript -- runnable snippet:

function * traverse(node) {
    let lead = node; // ...walks somewhere ahead of node
    let lag = null; // ... always follows one step behind node
    while (node) {
        yield node.data; // output
        lead.rightSibling = node.leftChild;
        while (lead.rightSibling) lead = lead.rightSibling;
        // rotate: point node to next right-sibling, and reverse direction of sibling edge
        [node.rightSibling, lag, node] = [lag, node, node.rightSibling]
    }
    
    // Restore tree
    lead = node = lag.rightSibling; // backwards
    lag.rightSibling = null;
    while (lead !== null && lead.leftChild === null) lead = lead.rightSibling; // actually going left!
    while (node) {
        if (lead !== null && lead.leftChild === lag) {
            // When lag is the leftChild of some node (lead), then lag should not be the target of a rightSibling
            [node.rightSibling, lag, node] = [null, node, node.rightSibling];
            // Find previous parent
            lead = lead.rightSibling;
            while (lead !== null && lead.leftChild === null) lead = lead.rightSibling; // actually going left!
        } else {
            // walk back and restore sibling pointers
            [node.rightSibling, lag, node] = [lag, node, node.rightSibling];
        }
    }
}

// Create node, given its data and child nodes
function Node(data, ...children) {
    // Link the children as siblings
    if (children.length > 1) children.reduceRight((a, b) => (b.rightSibling = a, b))
    // Create the node itself. For now, without any siblings
    return {
        data,
        leftChild: children.length ? children[0] : null,
        rightSibling: null
    };
}

// Example tree
let tree = Node(1, 
    Node(2, 
        Node(5), Node(6,
            Node(14), Node(15), Node(16)
        ), Node(7)
    ), Node(3,
        Node(8), Node(9)
    ), Node(4,
        Node(10), Node(11,
            Node(17), Node(18), Node(19)
        ), Node(12), Node(13)
    )
);

// Apply the algorithm and output the yielded values     
console.log(...traverse(tree)); 

Version in C

I am not so fluent in C, but I think this should do it:

#include <stdio.h>
#include <stdlib.h>

// define Node as a pointer to a node struct
typedef struct node {
    int data;
    struct node *leftChild;
    struct node *rightSibling;
} * Node;

// Some helper functions to ease the creation of a tree:
Node sibling(Node leftSibling, Node rightSibling) {
    leftSibling->rightSibling = rightSibling;
    return leftSibling;
}

Node parent(Node parent, Node child) {
    parent->leftChild = child;
    return parent;
}

Node create(int data) {
    Node node = malloc(sizeof(struct node));
    node->data = data;
    return node;
}
// end - helper functions

void traverse(Node node) {
    Node lead = node; // ...walks somewhere ahead of node
    Node lag = NULL; // ... always follows one step behind node
    while (node) {
        printf("%d\n", node->data); // output
        lead->rightSibling = node->leftChild;
        while (lead->rightSibling) lead = lead->rightSibling;
        // rotate: point node to next right-sibling, and reverse direction of sibling edge
        Node temp = node->rightSibling;
        node->rightSibling = lag;
        lag = node;
        node = temp;
    }

    // Restore tree
    lead = node = lag->rightSibling; // backwards
    lag->rightSibling = NULL;
    while (lead != NULL && lead->leftChild == NULL) lead = lead->rightSibling; // actually going left!
    while (node != NULL) {
        if (lead != NULL && lead->leftChild == lag) {
            // When lag is the leftChild of some node (lead), then lag should not be the target of a rightSibling
            lag = node;
            node = node->rightSibling;
            lag->rightSibling = NULL;
            // Find previous parent
            lead = lead->rightSibling;
            while (lead != NULL && lead->leftChild == NULL) lead = lead->rightSibling; // actually going left!
        } else {
            // walk back and restore sibling pointers
            Node temp = node->rightSibling;
            node->rightSibling = lag;
            lag = node;
            node = temp;
        }
    }
}

int main(void) {
    // Create the example tree
    Node root = parent(create(1), 
        sibling(parent(create(2), 
            sibling(create(5), sibling(parent(create(6),
                sibling(create(14), sibling(create(15), create(16)))
            ), create(7)))
        ), sibling(parent(create(3),
            sibling(create(8), create(9))
        ), parent(create(4),
            sibling(create(10), sibling(parent(create(11),
                sibling(create(17), sibling(create(18), create(19)))
            ), sibling(create(12), create(13))))
        )))
    );
    traverse(root);
    return 0;
}

To print the tree in a very basic format, you can use this function:

void printTree(Node node, int indent) {
    if (!node) return;
    for (int i = 0; i < indent; i++) printf("  ");
    printf("%d\n", node->data);
    printTree(node->leftChild, indent+1);
    printTree(node->rightSibling, indent);
}

This will help to verify that indeed the tree is the same before and after the traversal.

Answer 2

You can apply Morris level order traversal if you want to traverse your tree in constant space.You can refer here and here.

Answer 3

If you can store an extra next pointer in each node of the tree which points to the next node in level order for each level, then you can do the level order traversal in constant space.