Print bst in order python

Me and my friend are doing some school work with programming in Python 3.1 and are VERY stuck. We're programming a binary tree and it's working fine except when we want to print all the nodes in inorder in a way that would create a sentence (all the words in inorder just after one another in a row). We have been looking all over the internet for clues as to how to procede and we've been working with this little thing for like two hours. Any advice/help would be awesome.

Our program/Binary tree:

class Treenode:  
    def __init__(self, it = None, le = None, ri = None):  
        self.item = it  
        self.left = le  
        self.right = ri  

class Bintree:  
    def __init__(self):  
        self.item = None  
        self.left = None  
        self.right = None  

    def put(self, it = None):
        key = Treenode(it)
        if self.item == None:
            self.item = key
            return
        p = self.item
        while True:
            if key.item < p.item:
                if p.left == None:
                    p.left = key
                    return
                else:
                    p = p.left
            elif key.item > p.item:
                if p.right == None:
                    p.right = key
                    return
                else:
                    p = p.right
            else:
                return

    def exists(self, it):
        key = it
        p = self.item
        if p == key:
            return True
        while True:
            if key < p.item:
                if p.left == None:
                    return False
                else:
                    p = p.left
            elif key > p.item:
                if p.right == None:
                    return False
                else:
                    p = p.right
            else:
                return

    def isEmpty(self):
        if self.item == None:
            return True
        else:
            return False

def printtree (Treenode):
    if Treenode.left != None:
        printtree (Treenode.left)
    print (Treenode.item)
    if Treenode.right != None:
        printtree (Treenode.right)

We get a sort of print when we run the program which looks like this: "bintree.Treenode object at 0x02774CB0", which is not what we want.

We use the tree by running this:

import bintree

tree = bintree.Bintree()
print(tree.isEmpty())    # should give True
tree.put("solen")
print(tree.isEmpty())    # should give False
tree.put("gott")
tree.put("sin")
tree.put("hela")
tree.put("ban")
tree.put("upp")
tree.put("himlarunden")
tree.put("manen")
tree.put("seglar")
tree.put("som")
tree.put("en")
tree.put("svan")
tree.put("uti")
tree.put("midnattsstuden")

print(tree.exists("visa"))     # should give False
print(tree.exists("ban"))      # should give True
tree.printtree()               # print sorted

Also, the second last row gives us "None" instead of "True", which is wierd.

In addition to taking courses on Python, computer science, data structures, and algorithms, I have joined a few communities offering programming challenges to help me improve my coding skills. I enjoy these programming challenges, and recently finished the 30 Days of Code Challenge at HackerRank using both C# and Python.

One of the recent challenges I received was to code the inorder traversal of a binary search tree. The binary search tree was already created and I just needed to print all the nodes in correct order, which means I had to do a proper inorder traversal of the binary search tree and print the key of each node along the way.

Create Binary Search Tree in Python

First things first, I need a binary search tree in Python. Here is a barebones Node Class in Python along with a simple add function that will create a binary tree using level-order traversal.

from collections import deque


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


def add(node, root):
    if root is None:
        raise ValueError('root cannot be None.')

    nodes_found = deque([root])

    while len(nodes_found) > 0:
        current_node = nodes_found.popleft()

        if current_node.left is None:
            current_node.left = node
            break
        if current_node.right is None:
            current_node.right = node
            break

        nodes_found.append(current_node.left)
        nodes_found.append(current_node.right)

I can create a balanced, binary search tree using keys 1 - 15 using a simple script in Python.

root = Node(8)
keys = [4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]

for key in keys:
    add(Node(key), root)

I am essentially doing a level-order traversal (like breadth-first search) that adds these keys in a particular order to create a binary search tree. The order of the keys in the list is important.

Inorder Traversal of Binary Search Tree

Now that I have a binary search tree in Python, I need to perform an inorder traveral of the nodes to display the keys in their correct order. An inorder traveral will display a node's left sub-tree, then the value of its key, followed by the right sub-tree. An inorder traversal makes the most sense for binary search trees, because this is exactly the way binary search trees are ordered.

Here is a display_nodes Python function that displays each key of a binary search tree using inorder traversal.

def display_nodes(root):
    if root is None:
        return

    if root.left is not None:
        display_nodes(root.left)

    print(root.key, end=' ')

    if root.right is not None:
        display_nodes(root.right)

Here is a Python script that displays the nodes of the binary search tree created above.

display_nodes(root)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

Conclusion

In the programming challenge the binary search tree was already provided, so the code I wrote to create the binary search tree wasn't part of the challenge. I just wrote that really quickly in Python to set up the challenge. The only code I needed to write in Python ( I did it in C# as well ) was the display_nodes function, which is a recursive function that does an inorder traveral of the binary search tree. This challenge didn't take me long, but it's great to have these challenges to keep binary search trees fresh in my mind. As a freelance ASP.NET C# Web Developer I don't come across binary search trees in my daily development.

Hope this helps!

How do I print BST in ascending order?

How do you inorder a BST?

Can we construct BST from inorder?

How do I print descending order in BST?