Remove Node in Binary Search Tree
Source
Given a root of Binary Search Tree with unique value for each node. Remove the node with
given value. If there is no such a node with given value in the binary search tree, do nothing.
You should keep the tree still a binary search tree after removal.
Example
Given binary search tree:
5
/ \
3 6
/ \
2 4
Remove 3, you can either return:
5
/ \
2 6
\
4
or :
5
/ \
4 6
/
2
Java
public class Solution {
public TreeNode removeNode(TreeNode root, int value) {
if (root == null)
return null;
if (value < root.val)
root.left = removeNode(root.left, value);
else if (value > root.val)
root.right = removeNode(root.right, value);
else {
if (root.left == null)
return root.right;
if (root.right == null)
return root.left;
TreeNode x = root;
root = findMin(root.right);
root.right = deleteMin(x.right);
root.left = x.left;
}
return root;
}
public TreeNode findMin(TreeNode node){
while(node.left!=null){
node=node.left;
}
return node;
}
public TreeNode deleteMin(TreeNode node) {
if(node.left == null) {
return node.right;
}
node.left = deleteMin(node.left);
return node;
}
}
Reference
[LintCode]Remove Node in Binary Search Tree