Insert into a Binary Search Tree

Tested Python solution for LeetCode 701 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 701, Medium. Topics: Tree, Binary Search Tree, Binary Tree. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 14 parametrized pytest cases, and a playground notebook:

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

​

Problem

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

​

Examples

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]

​

Constraints

• The number of nodes in the tree will be in the range [0, 10^4].
• -10^8 <= Node.val <= 10^8
• All the values Node.val are unique.
• -10^8 <= val <= 10^8
• It’s guaranteed that val does not exist in the original BST.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

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

​

Complexity

Time	Space
O(h)	O(1)

​

Tags

NeetCode 250, NeetCode All.