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