Printing levels of Binary Search Tree

Question

I have a binary search tree data structure class that holds nodes which are objects in the side the class that acts like a binary search tree.

The class is too long to post here, but basically this is how it works. If I want to print the top value of the bst, I would say

print (self._root)

If I wanted to move to the left side of the tree (same with to go to the right, just put right instead of left) , I would say

print (self._root._left)

I hope this is enough so you can help me with my problem

So onto my problem, if I have a bst like:

I want to be able to print out:

I have written a recursive traverse function:

def traverse(self):

        a = []
        self._traverse_aux(self._root, a)   
        return a

def _traverse_aux(self, node, a):

        if node is not None:
            self._traverse_aux(node._left, a)
            a.append(node._value)
            self._traverse_aux(node._right, a)
        return

How ever, this prints the values in a single array:

[1, 3, 4, 6, 8, 10]

How can I get it to print the way I want above?

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) — alternate direction, Mar 19 '14 at 14:10

score 0 · Answer 1 · answered Mar 19 '14 at 14:08

Optimally, you're going to want to answer this recursively. This type of traversal in particular is called Breadth-First. Here are some notes on traversal of binary search trees which might be useful to you, although they are in java.

Here is also a very similar (possibly duplicate) question, although as opposed to solving it recursively a solution is given using loops.

Printing levels of Binary Search Tree

1 Answers1