Insert into a Binary Search Tree

lcpy gen -n 701   # by problem number
lcpy gen -s insert_into_a_binary_search_tree   # by problem name

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

![Example 1 alt](https://assets.leetcode.com/uploads/2020/10/05/bst.jpg)

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

from leetcode_py import TreeNode


class Solution:
    # Time: O(h)
    # Space: O(1)
    def insert_into_bst(self, root: TreeNode[int] | None, val: int) -> TreeNode[int] | None:
        node = TreeNode(val)
        if root is None:
            return node

        current = root
        while True:
            if val < current.val:
                if current.left is None:
                    current.left = node
                    return root
                current = current.left
            else:
                if current.right is None:
                    current.right = node
                    return root
                current = current.right