5

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

Improve this question
1
  • 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? Commented Jul 13, 2011 at 16:46

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Why do you want to traverse back up when printing the tree level by level?
Because there is no link directly to a node's sibling so you must first go through the parent.
Thanks I get it. Seems will work but I ll have to figure out a concrete algorithm first.
@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.
@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).
|
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

Improve this answer

Comments

1

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);
}
Improve this answer

2 Comments

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)
This actually processes only 2n nodes if the tree is perfectly balanced. Not so bad.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.