BST insert using recursive

[hichipi12]

I am working on implementing an insert function in BST. When I print out the bst out, there are two true and two false. It supposed to be all true. I do not know what have i done wrong. I would appreciate if anyone can help me

class BTNode:
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right
class BST:
    def __init__(self):
        # reference to root node - do not modify
        self.root = None
    def insert(self, value):
        '''Takes a numeric value as argument.
        Inserts value into tree, maintaining correct ordering.
        Returns nothing.
        recursive, may use helper function'''
        if self.root is None:
            self.root = BTNode(value, None, None)
        else:
            self.insert_helper(value, self.root)
# self.root = node in the parameter
    def insert_helper(self, value, current_node):
        if value < current_node.value:
            if current_node.left is None:
                current_node.left = BTNode(value, None, None)
            else:
                self.insert_helper(value, current_node.left)
        elif value > current_node.value is None:
            if current_node.right:
                current_node.right = BTNode(value, None, None)
            else:
                self.insert_helper(value, current_node.right)
    def search(self, value):
        if self.root:
            value_found = self.search_helper(value, self.root)
            if value_found:
                return True
            return False
        else:
            return None
    def search_helper(self, value, cur_node):
        if value > cur_node.value and cur_node.right:
            return self.search_helper(value, cur_node.right)
        elif value < cur_node.value and cur_node.left:
            return self.search_helper(value, cur_node.left)
        if value == cur_node.value:
            return True

bst = BST()
for value in [4, 2, 5, 3, 1, 6, 7]:
    bst.insert(value)
print(bst.search(1))
print(bst.search(2))
print(bst.search(6))
print(bst.search(7))

Output:
True
True
False
False

[deanhystad]

Your tree doesn't have any right branches which is likely caused by this:

        elif value > current_node.value is None:
            if current_node.right:
                current_node.right = BTNode(value, None, None)
            else:
                self.insert_helper(value, current_node.right)

Start with "value > current_node.value is None" which is gibberish. But even if that is made to work you have a problem with the next statement erasing an existing right node.

Don't assume everyone knows what BST stands for.

[hichipi12]

Your tree doesn't have any right branches which is likely caused by this:

        elif value > current_node.value is None:
            if current_node.right:
                current_node.right = BTNode(value, None, None)
            else:
                self.insert_helper(value, current_node.right)

Start with "value > current_node.value is None" which is gibberish. But even if that is made to work you have a problem with the next statement erasing an existing right node.

Don't assume everyone knows what BST stands for.

Omg thank you, It was such a dump mistake that I made, and I will be clear about term and keyword next timr. Thank you so much!

[deanhystad]

A few suggestions you can feel free to ignore.

You can specify default values for function arguments. It cleans the code up a bit, especially since your BST always initializes left and right to None. The class still has a way to specify a left and right branch in the __init__, so you aren't losing any functionality.

You should put some whitespace between modules and classes. This makes them easier to find.

I rewrote the code to use embedded helper functions. You are never going to call these directly from outside the class, so there is no reason having them muck up the class namespace.

"""Binary Search Tree
A binary search tree is a list of linked nodes that contain a value.  Each node has a left
and a right link.  The tree is arranged such that that all values in the left link are
less than the node value.  Searching through the tree is very quick because each comparison
cuts the remaining search roughly in half.
"""
class BinaryTreeNode:
    """Node in a binary search tree"""
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class BinarySearchTree:
    """Binary search tree.  Sort values so left < value"""
    def __init__(self):
        self.root = None

    def insert(self, value):
        """Insert value into tree"""

        def helper(value, node):
            """Search for place to insert value"""
            if value < node.value:
                if node.left:
                    helper(value, node.left)
                else:
                    node.left = BinaryTreeNode(value)
            elif value > node.value:
                if node.right:
                    helper(value, node.right)
                else:
                    node.right = BinaryTreeNode(value)

        if self.root is None:
            self.root = BinaryTreeNode(value)
        else:
            helper(value, self.root)

    def search(self, value):
        """Return True if value found in tree"""

        def helper(value, node):
            """Return True if value found in tree"""
            if not node:
                return False
            if node.value == value:
                return True
            if value < node.value:
                return helper(value, node.left)
            return helper(value, node.right)

        return helper(value, self.root)

[hichipi12]

oh I see. I often just try to work on the problems without thinking about the designing aspect of it. Thank you for such good example of such organize and clean code

[bterwijn]

You can use:

https://pypi.org/project/memory-graph/

to graph your data to better understand your code. Here I have taken your old code with the bug and added a line after inserting all the values that draws a graph of your tree:

import memory_graph as mg # see link above for install instructions

class BTNode:
    def __init__(self, value, left, right):
        self.left = left
        self.value = value # 'value' in the middle looks better
        self.right = right
        
class BST:
    def __init__(self):
        # reference to root node - do not modify
        self.root = None
    def insert(self, value):
        '''Takes a numeric value as argument.
        Inserts value into tree, maintaining correct ordering.
        Returns nothing.
        recursive, may use helper function'''
        if self.root is None:
            self.root = BTNode(value, None, None)
        else:
            self.insert_helper(value, self.root)
            
    def insert_helper(self, value, current_node):
        if value < current_node.value:
            if current_node.left is None:
                current_node.left = BTNode(value, None, None)
            else:
                self.insert_helper(value, current_node.left)
        elif value > current_node.value is None:
            if current_node.right:
                current_node.right = BTNode(value, None, None)
            else:
                self.insert_helper(value, current_node.right)
                
    def search(self, value):
        if self.root:
            value_found = self.search_helper(value, self.root)
            if value_found:
                return True
            return False
        else:
            return None
        
    def search_helper(self, value, cur_node):
        if value > cur_node.value and cur_node.right:
            return self.search_helper(value, cur_node.right)
        elif value < cur_node.value and cur_node.left:
            return self.search_helper(value, cur_node.left)
        if value == cur_node.value:
            return True
 
bst = BST()
for value in [4, 2, 5, 3, 1, 6, 7]:
    bst.insert(value)
mg.show(locals()) # <----------------- draw graph
print(bst.search(1))
print(bst.search(2))
print(bst.search(6))
print(bst.search(7))

The result is this graph that shows that some values are missing and that 'right' is always 'None':



After seeing such a graph of your data, it will in the future hopefully be easier to fix any remaining bugs.

Full disclosure: I am the developer of memory_graph.