450. Delete Node in a BST.md

450. Delete Node in a BST

---

leetcode Daily Challenge on August 31th, 2020.

---

Difficulty : Medium

Related Topics : Tree

---

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

• Search for a node to remove.
• If the node is found, delete the node.

Note

• Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

---

Solution

• mine
  • Java
    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 40.4 MB, less than 38.96% of Java online submissions

      // O(D)time
      // O(D)space
      // D = the delete node depth
      public TreeNode deleteNode(TreeNode root, int key) {
          root = dfs(root,key);
          return root;
      }
      
      TreeNode dfs(TreeNode node, int key) {
          if (node == null) return null;
          if (node.val == key) {
              if (node.left == null && node.right == null) {
                  return null;
              }
              boolean hasLeft = node.left != null;
              node.val = find(hasLeft ? node.left : node.right, hasLeft);
              TreeNode t = node;
              if (hasLeft) {
                  if (t.left.val == node.val) {
                      t.left = t.left.left;
                  } else {
                      t = t.left;
                      while (t.right != null) {
                          if (t.right.val == node.val) {
                              t.right = t.right.left;
                              break;
                          } else {
                              t = t.right;
                          }
                      }
                  }
              } else {
                  if (t.right.val == node.val) {
                      t.right = t.right.right;
                  } else {
                      t = t.right;
                      while (t.left != null) {
                          if (t.left.val == node.val) {
                              t.left = t.left.right;
                              break;
                          } else {
                              t = t.left;
                          }
                      }
                  }
              }
          } else if (node.val > key) {
              node.left = dfs(node.left, key);
          } else {
              node.right = dfs(node.right, key);
          }
          return node;
      }
      
      int find(TreeNode node, boolean left) {
          TreeNode t = node;
          int res;
          if (left) {
              while (t.right != null) {
                  t = t.right;
              }
              res = t.val;
          } else {
              while (t.left != null) {
                  t = t.left;
              }
              res = t.val;
          }
          return res;
      }
      

---

• the most votes

• Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.8 MB, less than 78.30% of Java online submissions

  public TreeNode deleteNode(TreeNode root, int key) {
      if(root == null){
          return null;
      }
      if(key < root.val){
          root.left = deleteNode(root.left, key);
      }else if(key > root.val){
          root.right = deleteNode(root.right, key);
      }else{
          if(root.left == null){
              return root.right;
          }else if(root.right == null){
              return root.left;
          }
  
          TreeNode minNode = findMin(root.right);
          root.val = minNode.val;
          root.right = deleteNode(root.right, root.val);
      }
      return root;
  }
  
  TreeNode findMin(TreeNode node){
      while(node.left != null){
          node = node.left;
      }
      return node;
  }
  

---