701. Insert into a Binary Search Tree
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:
The number of nodes in the tree will be in the range [0, 104].
-108 <= Node.val <= 108
All the values Node.val are unique.
-108 <= val <= 108
It's guaranteed that val does not exist in the original BST.
Original Page
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){
root = new TreeNode(val);
return root;
}
if(root.val<val){
root.right = insertIntoBST(root.right, val);
}else{
root.left = insertIntoBST(root.left, val);
}
return root;
}
450. Delete Node in a BST
* Wrong Code
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null){
return root;
}
TreeNode parent = root;
TreeNode cur = root;
boolean isLeft = false;
while(cur!=null){
if(cur.val > key){
parent = cur;
cur = cur.left;
isLeft = true;
}else if(cur.val < key){
parent = cur;
cur = cur.right;
isLeft = false;
}
// Main logic I will move all key's right node to replace pre-key position logic also we can do it with left node but not here
else{
//1. leaf node
if(cur.left == null && cur.right == null){
parent = linkToParent(parent, null, isLeft,root==cur);
}
else if(cur.right == null){
parent = linkToParent(parent, cur.left, isLeft,root==cur);
}
else if(cur.left == null){
parent = linkToParent(parent, cur.right, isLeft,root==cur);
}
// long logic for delete when key has both left and right child
else{
if(cur.right.left == null){
cur.right.left = cur.left;
parent = linkToParent(parent, cur.right, isLeft,root==cur);
}
else{
TreeNode rightParent = cur.right;
TreeNode leftest = cur.right;
while(leftest.left !=null){
rightParent = leftest;
leftest = leftest.left;
}
// main logic
parent = linkToParent(parent, leftest, isLeft,root==cur);
leftest.left = cur.left;
leftest.right = cur.right;
// now we find the least element in element's right subtree
if(leftest.right == null){
rightParent.left = null;
}
// the least element in right subtree has right child
else{
rightParent.left = leftest.right;
}
}
}
}
break;
}
return root;
}
public TreeNode linkToParent(TreeNode parent, TreeNode replace, boolean isLeft, boolean isRoot){
if(isRoot){
parent = replace;
}else{
if(isLeft){
parent.left = replace;
}else{
parent.right = replace;
}
}
return parent;
}
Top comments (0)