> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/04-11-2022-450.-delete-node-in-a-bst.md).

# 04/11/2022 450. Delete Node in a BST

{% embed url="<https://www.youtube.com/watch?v=WeoNeaQmMuo>" %}

```
// Some code
public int predecessor(TreeNode root) {
    root = root.left;
    while (root.right != null) root = root.right;
    return root.val;
  }
  
  root.val = predecessor(root);
  root.left = deleteNode(root.left, root.val);
  
```

```
// Some code

public int successor(TreeNode root) {
    root = root.right;
    while (root.left != null) root = root.left;
    return root.val;
  }
  
  root.val = successor(root);
  root.right = deleteNode(root.right, root.val);
```

```
// Some code
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        root = delete(root,key);
        return root;
    }

    private TreeNode delete(TreeNode root, int key) {
        if (root == null) return null;

        if (root.val > key) {
            root.left = delete(root.left,key);
        } else if (root.val < key) {
            root.right = delete(root.right,key);
        } else {
            if (root.left == null && root.right == null) return null; //1
            if (root.left == null) return root.right;//2
            if (root.right == null) return root.left;//3
            // if the left and right are both not null.
            //find the predecessor and replace its value with root.val and then delete the duplicate value in the left subtree.
            TreeNode tmp = root.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            root.val = tmp.val;
            root.right = delete(root.right,tmp.val);
        }
        return root;
    }
}
```