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.
There may be multiple valid insertion ways as long as the tree remains a valid BST.
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,null,25]
Approach
- Use recursion to find the correct insertion point.
- If the node is
null, create a new TreeNode and return it. - If
val < root.val, insert it into the left subtree. - If
val > root.val, insert it into the right subtree. - Return the root node to maintain the tree structure.
Time & Space Complexity
- Time Complexity: O(n), where h is the height of the tree
- Space Complexity: O(n) due to recursion
var insertIntoBST = function(root, val) {
if (!root) return new TreeNode(val);
if (root.val < val) {
root.right = insertIntoBST(root.right, val);
} else {
root.left = insertIntoBST(root.left, val);
}
return root;
};
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int val) {
struct TreeNode* node = malloc(sizeof(struct TreeNode));
node->val = val;
node->left = node->right = NULL;
return node;
}
struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
if (!root) return createNode(val);
if (val < root->val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val)
root.left = insertIntoBST(root.left, val);
else
root.right = insertIntoBST(root.right, val);
return root;
}
}
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def insertIntoBST(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insertIntoBST(root.left, val)
else:
root.right = insertIntoBST(root.right, val)
return root
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public TreeNode InsertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val)
root.left = InsertIntoBST(root.left, val);
else
root.right = InsertIntoBST(root.right, val);
return root;
}
}
