Recursive Binary Search Tree Python

Question

I want to implement a binary search tree with element, left & right child and parent in python.

class BSTNode:
""" An internal node for a BST . """
def __init__(self, item):
 """ Initialise a BSTNode on creation, with value==item. """
 self._element = item
 self._leftchild = None
 self._rightchild = None
 self._parent = None
def __str__(self):
 node = self
 if node != None:
 s = str(node._element)
 if node._leftchild: 
 node._leftchild.__str__()
 s = str(node._element)
 s+= ' '
 elif node._rightchild:
 node._rightchild.__str__()
 s += str(node._element)
 else:
 return s
 else:
 return ''
def add(self, item):
 node = self
 if node:
 if item <node._element :
 if node._leftchild is None:
 node._leftchild = BSTNode(item)
 node._leftchild._parent = node
 else:
 node._leftchild.add(item)
 elif item > node._element:
 if node._rightchild is None:
 node._rightchild = BSTNode(item)
 node._rightchild._parent = node
 else:
 node._rightchild.add(item)
tree = BSTNode(3);
tree.add(7);
 print(tree.__str__());

I wrote this program, but when i run it, it outputs None, but it should output 3 7(the order is inorder traversal). Does anyone knows what i am doing wrong?

Answer 1

Your __str__ method is incorrect. Specifically, you call __str__() of the left and right children but don't do anything with the result. Also note that a node can have both left and right children (if...elif will only check for one). You're also not not returing s if you hit one of your if or elif blocks.

You can simplify it to:

def __str__(self):
 node = self
 if node != None:
 s = str(node._element)
 if node._leftchild: 
 s = node._leftchild.__str__() + s
 if node._rightchild:
 s += ' ' + node._rightchild.__str__()
 return s
 return ''