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?

slider slider · Accepted Answer · 2018-11-14T17:32:22

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 ''

Recursive Binary Search Tree Python

1 Answers