Printing out a binary search tree with slashes

Question

http://pastebin.com/dN9a9xfs

That's my code to print out the elements of a binary search tree. The goal is to display it in level order, with slashes connecting the parent to each child. So for instance, the sequence 15 3 16 2 1 4 19 17 28 31 12 14 11 0 would display after execution as:

         15
        /  \
       3    16
      / \     \
     2   4    19
    /     \   / \
   1      12 17 28
  /      /  \     \
 0      11  14    31

I've been working on it for a long time now, but I just can't seem to get the spacing/indentation right. I know I wrote the proper algorithm for displaying the nodes in the proper order, but the slashes are just off. This is the result of my code as is: http://imgur.com/sz8l1

I know I'm so close to the answer, since my display is not that far off from what I need, and I have a feeling it's a really simple solution, but for some reason I just seem to get it right.

Answer 1

I'm out of time for now, but here's a quick version. I did not read your code (don't know C++), so I don't know how close our solutions are.

I changed the output format slightly. Instead of / for the left node, I used | so I didn't have to worry about left spacing at all.

15
| \
3  16
|\   \
2 4   19
|  \  | \
1   | 17 28
|   |      \
0   12      31
    | \
    11 14

Here's the code. I hope you're able to take what you need from it. There are definitely some Pythonisms which I hope map to what you're using. The main idea is to treat each row of numbers as a map of position to node object, and at each level, sort the map by key and print them to the console iteratively based on their assigned position. Then generate a new map with positions relative to their parents in the previous level. If there's a collision, generate a fake node to bump the real node down a line.

from collections import namedtuple

# simple node representation. sorry for the mess, but it does represent the
# tree example you gave.
Node = namedtuple('Node', ('label', 'left', 'right'))
def makenode(n, left=None, right=None):
    return Node(str(n), left, right)
root = makenode(
    15,
    makenode(
        3,
        makenode(2, makenode(1, makenode(0))),
        makenode(4, None, makenode(12, makenode(11), makenode(14)))),
    makenode(16, None, makenode(19, makenode(17),
                                makenode(28, None, makenode(31)))))

# takes a dict of {line position: node} and returns a list of lines to print
def print_levels(print_items, lines=None):
    if lines is None:
        lines = []
    if not print_items:
        return lines

    # working position - where we are in the line
    pos = 0

    # line of text containing node labels
    new_nodes_line = []

    # line of text containing slashes
    new_slashes_line = []

    # args for recursive call
    next_items = {}

    # sort dictionary by key and put them in a list of pairs of (position,
    # node)
    sorted_pos_and_node = [
        (k, print_items[k]) for k in sorted(print_items.keys())]

    for position, node in sorted_pos_and_node:
        # add leading whitespace
        while len(new_nodes_line) < position:
            new_nodes_line.append(' ')
        while len(new_slashes_line) < position:
            new_slashes_line.append(' ')

        # update working position
        pos = position
        # add node label to string, as separate characters so list length
        # matches string length
        new_nodes_line.extend(list(node.label))

        # add left child if any
        if node.left is not None:
            # if we're close to overlapping another node, push that node down
            # by adding a parent with label '|' which will make it look like a
            # line dropping down
            for collision in [pos - i for i in range(3)]:
                if collision in next_items:
                    next_items[collision] = makenode(
                        '|', next_items[collision])

            # add the slash and the node to the appropriate places
            new_slashes_line.append('|')
            next_items[position] = node.left
        else:
            new_slashes_line.append(' ')

        # update working position
        len_num = len(node.label)
        pos += len_num

        # add some more whitespace
        while len(new_slashes_line) < position + len_num:
            new_slashes_line.append(' ')

        # and take care of the right child
        if node.right is not None:
            new_slashes_line.append('\\')
            next_items[position + len_num + 1] = node.right
        else:
            new_slashes_line.append(' ')

    # concatenate each line's components and append them to the list
    lines.append(''.join(new_nodes_line))
    lines.append(''.join(new_slashes_line))

    # do it again!
    return print_levels(next_items, lines)

lines = print_levels({0: root})
print '\n'.join(lines)