adding a node in Binary Search Tree

Question

I am currently working on implementing a Binary search tree but I have a problem with creating the add_node() function. I tried to make it in a recursive way, but the result was weird.

For example- If I run add_node(1), add_node(5), and add_node(0), my tree has only 1, no 5 and 0.

I would be happy if you tell me what the problem is.

def add_node(self, value: int) -> None:
        
    if self.root == None:
        self.root = Node(value)
        return

    else:
        return self.add_recursion(self.root, value)

def add_recursion(self, node: Node, value: int) -> None:
        
    if node == None:
        node = Node(value)
        return

    elif value < node.value:
        return self.add_recursion(node.left, value)

    else:
        return self.add_recursion(node.right, value)

Answer 1

When a None value is passed into a function, it is passed by value, not by reference, since... there is no reference.

    elif value < node.value:
        return self.add_recursion(node.left, value)

    else:
        return self.add_recursion(node.right, value)

When node.left or node.right is None, a Node ends up being created but not attached to node. So what you could do is handle the cases where they are None separately.

def add_recursion(self, node: Node, value: int) -> None:
    if node == None:
        node = Node(value)
    elif value < node.value:
        if node.left == None:
            node.left = Node(value)
        else:
            self.add_recursion(node.left, value)
    else:
        if node.right == None:
            node.right = Node(value)
        else:
            self.add_recursion(node.right, value)

While this is workable, it becomes quite ugly. Look at the answer by Locke to see a better way to structure your code.

Also, an additional tip for readability, avoid using return where they aren't necessary such as at the end of a flow.