Insert into BST

Insert a value into a Binary Search Tree and return the root.

binary-search-tree recursion tree insertion

You are given the root of a Binary Search Tree (BST) and an integer value to insert. Write a function `insert_into_bst(root, val)` that inserts the value into the BST and returns the root of the updated tree. The BST property must be maintained: for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. You may assume the value is not already present in the tree. If the root is `None`, return a new node with the given value. The function signature is `def insert_into_bst(root, val):`. The `TreeNode` class has attributes `val`, `left`, and `right`. In tests, nodes are represented as dictionaries in the format `{"val": ..., "left": ..., "right": ...}`. Your solution will run in an environment that automatically converts between `TreeNode` objects and dictionary representations for testing, so you can assume the environment handles the conversion for you.

Constraints

0 <= number of nodes <= 10^4
-10^9 <= Node.val <= 10^9
All Node.val are unique.
val is not already in the tree.
Time: O(H) where H is tree height, O(log N) average, O(N) worst.
Space: O(H) for recursion stack.

Example

>>> # Example 1: Insert 5 into [4,2,7,1,3]
>>> root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
>>> insert_into_bst(root, 5).right.left.val
5
>>> # Example 2: Insert into empty tree
>>> insert_into_bst(None, 5).val
5

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Compare the value with the current node's value to decide left or right.

If the child is None, place the new node there.

Recursion is natural: return the updated subtree root.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.