AAlgoLoopSpaced repetition for LeetCode
MEDIUMTree / RecursionLeetCode ↗

Insert into a Binary Search Tree

The key idea

A BST tells you exactly where a new value belongs: at every node, go left when the value is smaller and right when it is larger. You never need to compare against more than one node per level, so you slide down a single root-to-leaf path and hang the new node on the first empty (null) child slot you reach.

Problem

You are given the root node of a binary search tree (BST) and an integer val to insert into the tree. Insert val into the BST and return the root node of the BST after the insertion.

A BST keeps every node's left subtree strictly smaller and its right subtree strictly larger, so the new value has exactly one ordering-correct spot to land. The input is guaranteed to be a valid BST and val is guaranteed not to already exist in it.

It is guaranteed that the insertion always keeps the tree a valid BST. Note that there may be many valid ways to insert the value, and you may return any of them. If the tree is empty (root is null), the inserted value becomes the new root.

Constraints

Examples

Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5]
Input: root = [40,20,60,10,30,50,70], val = 25 Output: [40,20,60,10,30,50,70,null,25]
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 Output: [4,2,7,1,3,5]

Complexity

Time: O(h) Space: O(1)

See the full solution

410310
Step-by-step visualization
Start free →

More Tree / Recursion problems