Insert into Binary Tree Search

Always insert at a leaf:

1) The function is called recursively:

a) if the val is greater than the root val, if the right part is empy just add the val otherwise call recursively the function on the right part

b) if the val is smaller than the root val, if the left part is empy just add the val otherwise call recursively the function on the left part

2) Return the modified tree (special case if the initial Tree is empty then return a Tree just just the val as node value)

def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    def helper(root, val):
        if val >= root.val:
            if not root.right:
                root.right = TreeNode(val)
            else:
                helper(root.right, val)
        elif val < root.val:
            if not root.left:
                root.left = TreeNode(val)
            else:
                helper(root.left, val)

    if not root:
        return(TreeNode(val))

    helper(root, val)
    return(root)