Writing a Binary Search Tree algorithm: proper __str__(self) method needed

Python Help
1

I’m learning algorithm design.

Some time ago I completed a binary search algorithm.

I am now exploring Binary Search Trees.

I have a Python code snippet. After spending a considerable amount of time chasing many cryptic but trivial TypeErrors and NameErrors, passing in test data seems to work. The script runs. When I run it using my debugger, as I step through line by line with each pass, all the lower integer values are inserted to the left nodes and higher number integer nodes are inserted to the right. So it works.

The only detail as far as I can tell that remains outstanding is getting a valid string representation to work for more helpful output when the final test print statement is executed. My expected output is: ((18 21 ) 47 (52 76 (82) )) but my Python interpreter is returning the object’s hash location in memory. This is my main question for all of you. What would you people recommend I try instead to get the test print statement to show something more useful?

Any other comments / feedback / tips from the community here to help optimize and improve my script are welcome.

Thanks!

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    
class BST:
    def __init__(self):
        # newNode = Node(value)
        # self.root = newNode
        self.root = None

    def insert(self, value):
        newNode = Node(value)
        if self.root == None:
            self.root = newNode
            return self
        temp = self.root
        while True:
            if newNode.value == temp.value:
                return None
            if newNode.value < temp.value:
                if temp.left == None:
                    temp.left = newNode
                    return self
                temp = temp.left
            else:
                if temp.right == None:
                    temp.right = newNode
                    return self
                temp = temp.right
        
        def __str__(self):
            return self._str_recursive(self.root)

        def _str_recursive(self, node):
            if node is None:
                return "Empty Tree"
            return f"({self._str_recursive(node.left)} {node.value} {self._str_recursive(node.right)})"

mytree = BST()
mytree.insert(47)
mytree.insert(21)
mytree.insert(76)
mytree.insert(18)
mytree.insert(52)
mytree.insert(82)
print(mytree)
2

This is simply a typo; you have the __str__ and _str_recursive methods indented inside of insert, instead of putting them directly in the class. After fixing that I see no issue:

>>> print(mytree)
(((Empty Tree 18 Empty Tree) 21 Empty Tree) 47 ((Empty Tree 52 Empty Tree) 76 (Empty Tree 82 Empty Tree)))

(If you don’t want to see Empty Tree for all the leaf nodes, then don’t return it in the recursion; use an empty string instead. If you want something different for the special case where the entire tree is indeed empty, then put that special case outside the recursion - i.e., directly in __str__.)

As an aside, I recommend not making the insert method return self, for the same reasons that e.g. the built-in list’s insert method does not.

3

Try with this data:

mytree = BST()
mytree.insert(18)
mytree.insert(21)
mytree.insert(47)
mytree.insert(52)
mytree.insert(76)
mytree.insert(82)

Notice that the tree is 6 level deep. A search is worst case O(n) not the optimum O(log2(n)) that would be desirable for a binary tree.

% py3 a.py
(Empty Tree 18 (Empty Tree 21 (Empty Tree 47 (Empty Tree 52 (Empty Tree 76 (Empty Tree 82 Empty Tree))))))

You mission should you accept it is to change the code to balance the tree.