Problem Statement:
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:
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:
- The number of nodes in the tree will be in the range
[0, 104]. -108 <= Node.val <= 108- All the values
Node.valare unique. -108 <= val <= 108- It’s guaranteed that
valdoes not exist in the original BST.
Approach
- If the current node (
root) isnull, create and return a new node with valueval. - If
valis greater than the current node’s value, recursively insert into the right subtree. - Otherwise, recursively insert into the left subtree.
- Return the unchanged root after insertion.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(h)(h=tree height)
Dry Run
Function Call: insertIntoBST(root, 1) where
root = Node(5)
├── left: Node(3)
│ ├── left: Node(2)
│ │ └── left: null
│ │ └── right: null
│ └── right: Node(4)
└── right: Node(7)
├── left: Node(6)
└── right: Node(8)
Step 1:
→ insertIntoBST(curr = 5, val = 1)
→ 1 < 5 → go left
→ insertIntoBST(curr = 3, val = 1)
→ 1 < 3 → go left
→ insertIntoBST(curr = 2, val = 1)
→ 1 < 2 → go left
→ insertIntoBST(curr = null, val = 1)
→ return new TreeNode(1)
→ Node(2).left = Node(1)
→ return Node(2)
→ Node(3).left = Node(2)
→ return Node(3)
→ Node(5).left = Node(3)
→ return Node(5)
Final Tree Structure:
root = Node(5)
├── left: Node(3)
│ ├── left: Node(2)
│ │ └── left: Node(1)
│ └── right: Node(4)
└── right: Node(7)
├── left: Node(6)
└── right: Node(8)
Final Result: Node(5) – the tree with value 1 inserted at the correct position.
root = Node(5)
├── left: Node(3)
│ ├── left: Node(2)
│ │ └── left: null
│ │ └── right: null
│ └── right: Node(4)
└── right: Node(7)
├── left: Node(6)
└── right: Node(8)
Step 1:
→ insertIntoBST(curr = 5, val = 1)
→ 1 < 5 → go left
→ insertIntoBST(curr = 3, val = 1)
→ 1 < 3 → go left
→ insertIntoBST(curr = 2, val = 1)
→ 1 < 2 → go left
→ insertIntoBST(curr = null, val = 1)
→ return new TreeNode(1)
→ Node(2).left = Node(1)
→ return Node(2)
→ Node(3).left = Node(2)
→ return Node(3)
→ Node(5).left = Node(3)
→ return Node(5)
Final Tree Structure:
root = Node(5)
├── left: Node(3)
│ ├── left: Node(2)
│ │ └── left: Node(1)
│ └── right: Node(4)
└── right: Node(7)
├── left: Node(6)
└── right: Node(8)
Final Result: Node(5) – the tree with value 1 inserted at the correct position.
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;
};
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 root.val < val:
root.right = insertIntoBST(root.right, val)
else:
root.left = insertIntoBST(root.left, val)
return root
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) {
val = x;
left = right = null;
}
}
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (root.val < val) {
root.right = insertIntoBST(root.right, val);
} else {
root.left = insertIntoBST(root.left, val);
}
return root;
}
}
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* insertIntoBST(TreeNode* root, int 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;
}
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* newNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = node->right = NULL;
return node;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) return newNode(val);
if (root->val < val) {
root->right = insertIntoBST(root->right, val);
} else {
root->left = insertIntoBST(root->left, val);
}
return root;
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0) {
this.val = val;
this.left = null;
this.right = null;
}
}
public class Solution {
public TreeNode InsertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (root.val < val) {
root.right = InsertIntoBST(root.right, val);
} else {
root.left = InsertIntoBST(root.left, val);
}
return root;
}
}
