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

I am not sure about it, but cant we modify the node`s structure to contain the level information into it?? And, so by any traversal we can initialise all the nodes with their proper levels, and by another traversal, maybe, print all the nodes along with their level numbers? — letsc, Jul 13 '11 at 16:46

score 5 · Accepted Answer · answered Apr 06 '11 at 13:40

5

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.

answered Apr 06 '11 at 13:40

Jerry Coffin

476,176
80
629
1,111

Why do you want to traverse back up when printing the tree level by level? – Codier Apr 06 '11 at 13:44
Because there is no link directly to a node's sibling so you must first go through the parent. – Dave Rager Apr 06 '11 at 13:48
Thanks I get it. Seems will work but I ll have to figure out a concrete algorithm first. – Codier Apr 06 '11 at 13:50
@Codier: as Dave Rager pointed out, you need to. You also (usually) want to print the root centered over its descendants, in which case you need to know how many descendants are going to end up to its left. – Jerry Coffin Apr 06 '11 at 14:08
@Jerry Coffin: Where would we be storing the child->parent pointer? – MAK Apr 06 '11 at 15:25
1

@MAK: into the spot *normally* used for the node's pointer to its child (whichever child you're working with at the moment). It's a variation of the old trick for traversing a linked list forward and then back to the beginning by reversing each node's link, to point to its predecessor instead of its successor (and then switching it back as your go back toward the beginning). – Jerry Coffin Apr 06 '11 at 15:37
@JerryCoffin: The question asks for using constant memory, not no additional memory. I think _no_ additional memory is impossible. But for constant memory you don't need to tweak the pointers as you go. – Mooing Duck Jun 13 '14 at 23:17

score 3 · Answer 2 · edited May 23 '17 at 11:55

3

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

edited May 23 '17 at 11:55

Community

1
1

answered Apr 07 '11 at 21:01

brainydexter

19,826
28
77
115

score 1 · Answer 3 · answered Apr 08 '11 at 20:55

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);
}

This question can be solved without the log(n) extra memory on the call stack, but it's a bit trickier. (Also, if you're going to use recursion, there's a very simple algorithm that's way faster than this) — Mooing Duck, Jun 13 '14 at 23:19
This actually processes only `2n` nodes if the tree is perfectly balanced. Not so bad. — Jo So, Jun 14 '14 at 00:20

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

3 Answers3