Failed to insert value into Binary Search Tree

Question

I have some trouble on insertion function of BST.

It seems that there are no outputs return after running these code; however, I can't successfully insert value into the tree.

To be more precisely, while I used Spyder to check, the value of root is NoneType object of bulitins module. As the result, I pretty sure that I am failed to insert value into the tree. And I suspect that this is due to the NoneType of the root, but even if I tried to give root a value before running the code by root = TreeNode(3) then Solution().insert(root, 5). I am unsure of how to resolve this.

Please have a look at the following code.

class TreeNode():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution():    

    def insert(self, root, val):

        if root is None:
            root = TreeNode(val)
            return root
        else:
            if val <= root.val:
                if root.left:
                    root.left = self.insert(root.left, val)
            else:
                if root.right:
                    root.right = self.insert(root.right, val)
                return root


root = None
Solution().insert(root, 5)

any suggestion would be much appreciated!!

Answer 1

There is bug(you dont need to check if root.left: and if root.right: because in recursive calls you have handled the none condition) in your condition of recursive calls as well return statements that's only in right side of tree not for left side of tree so thats why its not working as per your expectation:

def insert(self, root, val):

    if root is None:
        root = TreeNode(val)
        return root
    else:
        if val <= root.val:
            root.left = self.insert(root.left, val)
        else:
            root.right = self.insert(root.right, val)
        return root

Here is link of working code : link