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:

    41
   /  \
  7   53
 / \  /
1  19 47

I want it to print like:

41

7
53

1
19
47

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())

Answer 1

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]]