python list from python binary tree

Question

I want to define a function which returns a list of the tree node values. The list is in level order (top to bottom, left to right).

For example, the list produced from the tree shown above would be: [2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None, end].

This is the Binary Tree implementation

class BinaryTree:

    def __init__(self, data, left = None, right = None):
        self.key = data
        self.left = left
        self.right  = right

    def insert(self, data):
        node = self
        while node is not None:
            parent = node
            if node.left is None:
                parent.insert_left(data)
                break
            if node.right is None:
                parent.insert_right(data)
                break
            node = node.left

    def insert_left(self, data):
        self.left = BinaryTree(data, left=self.left)  

    def insert_right(self, data):
        self.right = BinaryTree(data, right=self.right)

    def get_left_subtree(self):
        return self.left

    def set_left(self, tree):
        self.left = tree

    def set_right(self, tree):
        self.right = tree

    def get_right_subtree(self):
        return self.right

    def set_value(self, val):
        self.key = val

    def get_value(self):
        return self.key

    def create_string(self, indent):
        string = str(self.key) + '---+'
        if self.left:
            string += '\n(l)' + indent + self.left.create_string(indent + '    ')
        if self.right:
            string += '\n(r)' + indent + self.right.create_string(indent + '    ')
        return string

    def __str__(self):
        return self.create_string('  ')

http://stackoverflow.com/questions/5262308/how-do-implement-a-breadth-first-traversal — pvg, May 28 '16 at 06:09
The important thing here is the algorithm. You're looking for breadth-first traversal. You might want to check how this is different from what you have. — pvg, May 28 '16 at 06:12
Well, have you noticed your implementation is recursive, BFS implementations usually are not. — pvg, May 28 '16 at 06:15
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/113205/discussion-between-ross-c-and-pvg). — ross.c, May 28 '16 at 08:56

janos · Accepted Answer · 2016-05-28T13:09:00.727

For level-order traversal, an iterative algorithm is the most natural, for example:

def create_list(tree, templist=[]):
    """
    >>> tree = BinaryTree(2, BinaryTree(29, BinaryTree(26)), BinaryTree(4, None, BinaryTree(2, BinaryTree(9))))
    >>> create_list(tree)
    [2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None]

    """
    items = []
    queue = [tree]

    while queue:
        copy = queue[:]
        queue = []

        for item in copy:
            if item is None:
                items.append(None)
                queue.append(None)
                queue.append(None)
            else:
                items.append(item.key)
                queue.append(item.left)
                queue.append(item.right)

        if all((x is None for x in queue)):
            break

    return items

If you really really really want a recursive implementation:

def create_list_rec(tree, items=[], queue=[]):
    """
    >>> tree = BinaryTree(2, BinaryTree(29, BinaryTree(26)), BinaryTree(4, None, BinaryTree(2, BinaryTree(9))))
    >>> create_list_rec(tree)
    [2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None]

    """
    if not items and not queue:
        return create_list_rec(None, [], [tree])

    copy = queue[:]
    queue = []

    for item in copy:
        if item is None:
            items.append(None)
            queue.append(None)
            queue.append(None)
        else:
            items.append(item.key)
            queue.append(item.left)
            queue.append(item.right)

    if all((x is None for x in queue)):
        return items

    return create_list_rec(items, queue)

python list from python binary tree

1 Answers1