How to print a binary tree level by level? Interview question!

Question

How to print a binary tree level by level?

This is an interview question I got today. Sure enough, using a BFS style would definitely work. However, the follow up question is: How to print the tree using constant memory? (So no queue can be used)

I thought of converting the binary tree into a linked list somehow but have not come up with a concrete solution.

Any suggestions?

Thanks

Answer 1

Extending on what Jerry Coffin said, I had asked a question earlier about doing something similar using in-order traversal. It uses the same logic as explained by him.

Check it out here:

Explain Morris inorder tree traversal without using stacks or recursion

Answer 2

One way to avoid using extra memory (much extra, anyway) is to manipulate the tree as you traverse it -- as you traverse downward through nodes, you make a copy of its pointer to one of the children, then reverse that to point back to the parent. When you've gotten to the bottom, you follow the links back up to the parents, and as you go you reverse them to point back to the children.

Of course, that's not the whole job, but it's probably the single "trickiest" part.

Answer 3

You can do it by repeatedly doing an in-order traversal of the tree while printing only those nodes at the specified level. However, this isn't strictly constant memory since recursion uses the call stack. And it's super inefficient. Like O(n * 2^n) or something.

printLevel = 1;

while(moreLevels) {

    moreLevels = printLevel(root, 1, printLevel);
    printLevel++;
}

boolean printLevel(Node node, int currentLevel, int printLevel) {

    boolean moreLevels = false;

    if(node == null) {
        return(false);
    }

    else if(currentLevel == printLevel) {
        print the node value;
    }

    else {

        moreLevels |= printLevel(node.leftChild, currentLevel + 1, printLevel);
        moreLevels |= printLevel(node.rightChild, currentLevel + 1, printLevel);
    }

    return(moreLevels);
}