Print Binary Tree - Python

[Daniel94]

def show_2d(self):
    '''
    Show a pretty 2D tree based on the output of bfs_order_star(). None
    values are are replaced by stars ('*').

    For example, consider the following tree `t`:
                10
          5           15
       *     *     *     20

    The output of t.bfs_order_star() should be:
    [ 10, 5, 15, '*', '*','*', 20 ]
    '''

I already got the function bfs_order_star() working like it should. That is a function that returns an array with all of the nodes from a tree in breadth-first traversal, where the empty nodes are declared as '*'.

Any ides how I can write a function that prints a 2D tree based on the data from that array?

[ichabod801]

First you need the depth of the tree, which you can calculate from the list output. That will tell you how many items are in the last row of the 2d output. Then convert everything in the list output to strings, and determine the longest one. That will be the width for all of them. Now you can calculate the overall width: The (item width + 1) times (the number of items on the last row * 2 - 1). That accounts for the items on the last row, and the gaps for items on the previous rows. You add one to the item width to add a space between each item.

Then you go through the rows, figure out the number of items on each row, take those items from the list, and figure out how much space should be between each item. Use the join method on that much space between the items centered (another method) in their item width. Center all of that in the overall width.