| 65 | }; |
| 66 | |
| 67 | Tree* deleteNode(Tree *root, int val) |
| 68 | { |
| 69 | if(root==nullptr) |
| 70 | return nullptr; |
| 71 | else |
| 72 | { |
| 73 | if(root->val>val) |
| 74 | root->left=deleteNode(root->left,val); |
| 75 | else if(root->val<val) |
| 76 | root->right=deleteNode(root->right,val); |
| 77 | else |
| 78 | { |
| 79 | if(root->left!=nullptr) |
| 80 | { |
| 81 | Tree *temp=root->left; |
| 82 | Tree *trav=temp->right; |
| 83 | if(trav==nullptr) |
| 84 | { |
| 85 | temp->right=root->right; |
| 86 | root=temp; |
| 87 | } |
| 88 | else |
| 89 | { |
| 90 | while(trav->right!=nullptr) |
| 91 | { |
| 92 | temp=trav; |
| 93 | trav=trav->right; |
| 94 | } |
| 95 | temp->right=trav->left; |
| 96 | root->val=trav->val; |
| 97 | trav->left=NULL; |
| 98 | } |
| 99 | } |
| 100 | else if(root->right!=nullptr) |
| 101 | { |
| 102 | Tree *temp=root->right; |
| 103 | Tree *trav=temp->left; |
| 104 | if(trav==nullptr) |
| 105 | { |
| 106 | temp->left=root->left; |
| 107 | root=temp; |
| 108 | } |
| 109 | else |
| 110 | { |
| 111 | while(trav->left!=nullptr) |
| 112 | { |
| 113 | temp=trav; |
| 114 | trav=trav->left; |
| 115 | } |
| 116 | temp->left=trav->right; |
| 117 | root->val=trav->val; |
| 118 | trav->right=NULL; |
| 119 | } |
| 120 | } |
| 121 | else |
| 122 | root=nullptr; |
| 123 | } |
| 124 | return root; |