SHARE
TWEET

delete node from bst

a guest Oct 17th, 2019 108 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public TreeNode deleteNode(TreeNode root, int key) {
  12.         if (root == null){
  13.             return null;
  14.         }
  15.         TreeNode returnValue = root;
  16.         if(root.val == key){
  17.             if (root.left != null && root.right != null){
  18.                 TreeNode iterParent = root.left;
  19.                 while(iterParent.right != null){
  20.                     iterParent = iterParent.right;
  21.                 }
  22.                 iterParent.right = root.right;
  23.                 return root.left;
  24.             } else if (root.left != null && root.right == null){
  25.                 TreeNode newRoot = root.left;
  26.                 root = null;
  27.                 return newRoot;
  28.             } else {
  29.                 TreeNode newRoot = root.right;
  30.                 root = null;
  31.                 return newRoot;
  32.             }
  33.         }
  34.        
  35.         if (key < root.val){
  36.             if (root.left != null ){
  37.             findDelete(root, root.left, key);
  38.             }
  39.         } else if (root.right != null){
  40.             findDelete(root, root.right, key);
  41.         }
  42.         return returnValue;
  43.     }
  44.    
  45.     public void findDelete(TreeNode parent, TreeNode sub, int key){
  46.         if (sub == null) return;
  47.         if (sub.val == key){
  48.             if (sub.left != null){
  49.                 if (sub.left.val < parent.val){ //this means that you got to sub by going to the left
  50.                     parent.left = sub.left;
  51.                     if (sub.right != null){
  52.                         TreeNode iterParent = sub.left;
  53.                         TreeNode subLeftRight = sub.left.right; //since el que deje guindando es el right del sub, voy a buscar el proximo null dentro del right subtree de sub para ponerlo ahi
  54.                         while (subLeftRight != null){
  55.                             iterParent = subLeftRight;
  56.                             if (sub.right.val > subLeftRight.val){
  57.                                 subLeftRight = subLeftRight.right;
  58.                             } else {
  59.                                 subLeftRight = subLeftRight.left;
  60.                             }
  61.                         }
  62.                         iterParent.right = sub.right;  
  63.                     }
  64.                     return;
  65.                 } else { //this means that you got to sub by going to the right
  66.                     parent.right = sub.left;
  67.                     if (sub.right != null){
  68.                         TreeNode iterParent = sub.left;
  69.                         TreeNode subLeftRight = sub.left.right; //since el que deje guindando es el left del sub, voy a buscar el proximo null dentro del left subtree de sub para ponerlo ahi
  70.                         while (subLeftRight != null){
  71.                             iterParent = subLeftRight;
  72.                             if (sub.right.val > subLeftRight.val){
  73.                                 subLeftRight = subLeftRight.right;
  74.                             } else {
  75.                                 subLeftRight = subLeftRight.left;
  76.                             }
  77.                         }
  78.                         iterParent.right = sub.right;  
  79.                     }
  80.                 }
  81.                 return;
  82.             }
  83.             if (sub.right != null){
  84.                 if (sub.right.val < parent.val){ //this means that you got to sub by going to the right
  85.                     parent.left = sub.right;
  86.                     if (sub.left != null){
  87.                         TreeNode iterParent = sub.right;
  88.                         TreeNode subRightLeft = sub.right.left; //since el que deje guindando es el right del sub, voy a buscar el proximo null dentro del right subtree de sub para ponerlo ahi
  89.                         while (subRightLeft != null){
  90.                             iterParent = subRightLeft;
  91.                             if (sub.left.val < subRightLeft.val){
  92.                                 subRightLeft = subRightLeft.left;
  93.                             } else {
  94.                                 subRightLeft = subRightLeft.right;
  95.                             }
  96.                         }
  97.                         iterParent.left = sub.left;
  98.                     }
  99.                     return;
  100.                 } else { //this means that you got to sub by going to the right
  101.                     parent.right = sub.right;
  102.                     if (sub.left != null){
  103.                         TreeNode iterParent = sub.right;
  104.                         TreeNode subRightLeft = sub.right.left; //since el que deje guindando es el right del sub, voy a buscar el proximo null dentro del right subtree de sub para ponerlo ahi
  105.                         while (subRightLeft != null){
  106.                             iterParent = subRightLeft;
  107.                             if (sub.left.val < subRightLeft.val){
  108.                                 subRightLeft = subRightLeft.left;
  109.                             } else {
  110.                                 subRightLeft = subRightLeft.right;
  111.                             }
  112.                         }
  113.                         iterParent.left = sub.left;
  114.                     }
  115.             }
  116.                 return;
  117.         }
  118.         if (key > parent.val){
  119.             parent.right = null;
  120.         } else {
  121.             parent.left = null;
  122.         }
  123.     }
  124.     if (key < sub.val){
  125.         findDelete(sub, sub.left, key);
  126.     } else {
  127.         findDelete(sub, sub.right, key);
  128.     }
  129.     }
  130. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top