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.
Example 1:
Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5] Explanation: Another accepted tree is:
Example 2:
Input: root = [40,20,60,10,30,50,70], val = 25 Output: [40,20,60,10,30,50,70,null,null,25]
Example 3:
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 Output: [4,2,7,1,3,5]
Constraints:
[0, 104].-108 <= Node.val <= 108Node.val are unique.-108 <= val <= 108val does not exist in the original BST.In this approach, we start from the root and traverse the tree to find an appropriate place for the new node without recursion. At each step, we decide to move left or right depending on the value of the node compared to the value we want to insert. Once we find a suitable spot, we insert the new node as a leaf and return.
This code creates a new tree node with the given value and traverses the tree starting from the root to find the correct insertion point. It uses a loop to move left or right in the tree and finally attaches the new node as a leaf.
C++
Java
Python
C#
JavaScript
Time Complexity: O(h) where h is the height of the tree. Space Complexity: O(1) since no extra space is utilized.
In the recursive method, we start at the root and recursively call the function for either the left or right subtree, based on comparisons, until an appropriate leaf is found for insertion. This method utilizes the call stack to keep track of previous nodes.
This recursive solution calls itself for the relevant subtree until a leaf node is found where the new node fits, maintaining BST properties at each recursive step.
C++
Java
Python
C#
JavaScript
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h), due to the recursive stack space.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(h) where h is the height of the tree. Space Complexity: O(1) since no extra space is utilized. |
| Recursive Approach | Time Complexity: O(h), where h is the height of the tree. |
How to solve (almost) any binary tree coding problem • Inside code • 224,586 views views
Watch 9 more video solutions →Practice Insert into a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor