Printing binary tree level order

[admiralfirelam]

Anybody know an algorithm for printing a binary tree using level order traversal but also so that the output is formatted to look like the actual conceptual version of the tree?

Ex:
N = Node key

N1
N2 N3
N4 N5 N6 N7
N8 N9 N10 N11 N12 N13 N14 N15

........................... etc..

[Duthomhas]

Google "breadth first"

[helios]

Or just look in Wikipedia.

[Hammurabi]

Assuming you know the basics of "level-order" (breadth-first) traversal, your problem is spacing out the node names to represent the tree.

One problem is that the tree can be very wide at the base. So you should print the tree vertically unless it's not too tall (say a height of 3, that's 4 levels including the root; that gives a base of 16 nodes; counting 3 letters per node name and 3 spaces between them, that's 93 characters already at the base).

I'll assume your tree is short and you want to print it horizontally, like this:

                                             height
                     N1                         0
         N2                      N3             1
   N4          N5          N6          N7       2
N8    N9    N10   N11   N12   N13   N14   N15   3

In the tree above, 21 spaces must be output before "N1". The number can be calculated from the height of the tree (where NodeNameLen is 3 in the diagram above):

(1 << height - 1) * NodeNameLen

Anyway, that's the kind of thinking you've got to do.