Print Levels Of A Binary Tree by Level Iteratively

Question

I want to print a binary tree level by level iteratively without using a dequeue or any other data structure besides a python list. I have looked online and most do it one of those ways mentioned above.

If I have a tree:

I want it to print like:

This is my shot at it but it doesn't print out all the values in the bst:

def levelorder(self):

        current = self._root
        current_left = current_right = self._root
        a = [current._value]

        while current_left is not None and current_right is not None:

            current_left = current_left._left
            current_right = current_right._right

            if current_left is not None:
                a.append(current_left._value)

            if current_right is not None:
                a.append(current_right._value)

        return a

This is what it outputs:

[41, 7, 53, 1]

Any ideas what is wrong with my code? and how I can approach the solution to this problem?

TREE CLASS:

class _BSTNode:

    def __init__(self, value):

        self._value = copy.deepcopy(value)
        self._left = None
        self._right = None
        self._height = 1
        return

class BST:

    def __init__(self):

        self._root = None
        self._count = 0
        self.comparisons = 0
        return

    def levelorder(self):


        levels = [[self._root]]

        while levels[-1]:

            nextlevel = []
            for node in levels[-1]:
                nextlevel.extend([node for node in (node._left, node._right) if node])

            levels.append(nextlevel)
        return levels[:-1]

and my main part:

b = BST()
b.insert(41)
b.insert(7)
b.insert(53)
b.insert(1)
b.insert(19)
b.insert(47)

print (b.levelorder())

This seems like it has been already answered [here](http://stackoverflow.com/questions/14815765/how-to-traverse-a-binary-tree-with-a-recursive-generator) — bosnjak, Mar 19 '14 at 20:16
@Lawrence The title indicates that an iterative solution is sought. — Hyperboreus, Mar 19 '14 at 20:17
possible duplicate of [Printing BFS (Binary Tree) in Level Order with \_specific formatting\_](http://stackoverflow.com/questions/1894846/printing-bfs-binary-tree-in-level-order-with-specific-formatting) — hivert, Mar 19 '14 at 23:04
@hivert that solution iterates on the best, my bst is different and is not iterable — l00kitsjake, Mar 20 '14 at 00:58

Hyperboreus · Accepted Answer · 2014-03-19T20:40:01.880

Without testing, as I don't have your Tree class, but I hope the general idea applies:

def levelorder(tree):
    levels = [ [tree.root] ]
    while levels [-1]:
        nextLevel = []
        for node in levels [-1]:
            nextLevel.extend ( [node for node in (node.left, node.right) if node] )
        levels.append (nextLevel)
    return levels # or maybe levels [:-1]

Fully working example:

#! /usr/bin/python3

class Node:
    def __init__(self, payload, left = None, right = None):
        self.payload = payload
        self.left = left
        self.right = right

    def __repr__(self):
        return self.payload

class Tree:
    def __init__(self, root):
        self.root = root

    def levels(self):
        levels = [[self.root]]
        while levels[-1]:
            nextLevel = []
            for node in levels[-1]:
                nextLevel.extend([node for node in (node.left, node.right) if node])
            levels.append(nextLevel)
        return levels[:-1]

t = Tree(Node('41', Node('7', Node('1'), Node('19')), Node('53', Node('47'))))

print(t.levels())

Output is [[41], [7, 53], [1, 19, 47]]

If I post my tree class, could you edit the above solution? Im still having some trouble with the implementation. — l00kitsjake, Mar 19 '14 at 20:36
Your example helped me a bit regarding understanding it, but mine still returns a list full of <__main__._BSTNode object at 0x100683b90>, etc.. I have added my tree class to the original question. Any ideas what i am still doing wrong? — l00kitsjake, Mar 19 '14 at 21:26
@Kalvin94 My code also returns a list of lists of `Node` objects, only that I have implemented `__repr__`. Take the final output, access `_value` of each member and you are set. Something like `\n\n'.join ('\n'.join (node._value for node in level) for level in tree.levels () )` — Hyperboreus, Mar 20 '14 at 02:22

Print Levels Of A Binary Tree by Level Iteratively

1 Answers1