Printing binary tree in python

Question

I want to print my binary tree vertical and the nodes should be random numbers, but output that I get is not what I want. For example I receive something like this:

497985
406204
477464

But program should print this:

.....497985
406204
.....477464

I don't know where is the problem. Im begginer at programming so if anyone can help me it would be great.

from numpy.random import randint
import random
from timeit import default_timer as timer


class binarytree:
    def __init__(self):
        self.elem = 0
        self.left = None
        self.right = None


def printtree(tree, h):
    if tree is not None:
        printtree(tree.right, h+1)
        for i in range(1, h):
            print(end = ".....")
        print(tree.elem)
        printtree(tree.left, h+1)


def generate(tree, N, h):
    if N == 0:
        tree = None
    else:
        tree = binarytree()
        x = randint(0, 1000000)
        tree.elem = int(x)
        generate(tree.left, N // 2, h)
        generate(tree.right, N - N // 2 - 1, h)
    printtree(tree, h)

tree = binarytree()
generate(tree, 3, 0)

Answer 1

I've re-written your code to be a little more Pythonic, and fixed what appeared to be some bugs:

from  random import randrange

class BinaryTree:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    @classmethod
    def generate_random_tree(cls, depth):
        if depth > 0:
            return cls(randrange(1000000),
                       cls.generate_random_tree(depth - 1),
                       cls.generate_random_tree(depth - 1))
        return None

    def __str__(self):
        """
        Overloaded method to format tree as string
        """
        return "\n".join(self._format())

    def _format(self, cur_depth=0):
        """
        Format tree as string given current depth. This is a generator of
        strings which represent lines of the representation.
        """
        if self.right is not None:
            yield from self.right._format(cur_depth + 1)
        yield "{}{}".format("." * cur_depth, self.val)
        if self.left is not None:
            yield from self.left._format(cur_depth + 1)

print(BinaryTree.generate_random_tree(4))
print()
print(BinaryTree(1,
                 BinaryTree(2),
                 BinaryTree(3,
                            BinaryTree(4),
                            BinaryTree(5))))

This outputs a tree, which grows from the root at the middle-left to leaves at the right:

...829201
..620327
...479879
.746527
...226199
..463199
...498695
987559
...280755
..168727
...603817
.233132
...294525
..927571
...263402

..5
.3
..4
1
.2

Here it's printed one random tree, and one tree that I manually constructed. I've written it so that the "right" subtree gets printed on top - you can switch this around if you want.

You can make some further adjustments to this by making more dots at once (which I think was your h parameter?), or adapting bits into whatever program structure you want.

This code works because it makes sure it builds a whole tree first, and then later prints it. This clear distinction makes it easier to make sure you're getting all of it right. Your code was a little confused in this regard - your generate function did instantiate a new BinaryTree at each call, but you never attached any of them to each other! This is because when you do tree = ... inside your function, all you're doing is changing what the local name tree points to - it doesn't change the attribute of the tree from higher up that you pass to it!

Your generate also calls printtree every time, but printtree also calls itself... This just doesn't seem like it was entirely right.

In my program, this bit generates the random tree:

    def generate_random_tree(cls, depth):
        if depth > 0:
            return cls(randrange(1000000),
                       cls.generate_random_tree(depth - 1),
                       cls.generate_random_tree(depth - 1))
        return None

The classmethod bit is just some object-oriented Python stuff that isn't very important for the algorithm. The key thing to see is that it generates two new smaller trees, and they end up being the left and right attributes of the tree it returns. (This also works because I did a little re-write of __init__).

This bit basically prints the tree:

    def _format(self, cur_depth=0):
        """
        Format tree as string given current depth. This is a generator of
        strings which represent lines of the representation.
        """
        if self.right is not None:
            yield from self.right._format(cur_depth + 1)
        yield "{}{}".format("." * cur_depth, self.val)
        if self.left is not None:
            yield from self.left._format(cur_depth + 1)

It's a generator of lines - but you could make it directly print the tree by changing each yield ... to print(...) and removing the yield froms. The key things here are the cur_depth, which lets the function be aware of how deep in the tree it currently is, so it knows how many dots to print, and the fact that it recursively calls itself on the left and right subtrees (and you have to check if they're None or not, of course).

(This part is what you could modify to re-introduce h).