problems with BST in python

Question

I have my BST class build like this :

class BST:
"""A Binary Search Tree."""

def __init__(self: 'BST', container: list =None) -> None:
    """
    Initialize this BST by inserting the items from container (default [])
    one by one, in the order given.
    """
    # Initialize empty tree.
    self.root = None
    # Insert every item from container.
    if container:
        for item in container:
            self.insert(item)

def __str__(self: 'BST'):
    """
    Return a "sideways" representation of the items in this BST, with
    right subtrees above nodes above left subtrees and each item preceded
    by a number of TAB characters equal to its depth.
    """
    # Tricky to do iteratively so we cheat,
    # You could take up the challenge...
    return BST._str("", self.root)

def insert(self: 'BST', item: object) -> None:
    """
    Insert item into this BST.
    """
    # Find the point of insertion.
    parent, current = None, self.root
    while current:
        if item < current.item:
            parent, current = current, current.left
        else:  # item > current.item
            parent, current = current, current.right
    # Create a new node and link it in appropriately.
    new_node = _BSTNode(item)
    if parent:
        if item < parent.item:
            parent.left = new_node
        else:  # item > parent.item
            parent.right = new_node
    else:
        self.root = new_node

My problem is how to implement a contains function without using recursion. I have tried a couple loop methods but it always ended up with indent error.

What has your contains function looked like when you received errors? — masrtis
– masrtis, Commented Apr 2, 2014 at 23:53

spinlok · Accepted Answer · 2014-04-02 23:34:52Z

1

The contains method will look very similar to your insert method, but even simpler because all you have to do is check if the item exists. So, traverse the BST as usual and return False if you reach the end, or True if you find the element:

def contains(self, item):
    current = self.root
    while current:
        if item == current.item:
            return True
        if item < current.item:
            current = current.left
        else:
            current = current.right
    return False

answered Apr 2, 2014 at 23:34

spinlok

3,68123 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

problems with BST in python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related