Guest User

delete node from bst

a guest
Oct 17th, 2019
109
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