CODEWITHSUNDEEP
c++treebinary-search-tree
J. Doe
J. Doe

Reputation: 1341

Why doesn't this swap the two nodes?

I am trying to solve a question from leetcode - deleting a node from a BST. We would be given the root node of a BST and a key; and we have to deleted the node with that key as the value. We can assume that all the tree nodes have unique values. We have to return the root node post this operation. (question link is: https://leetcode.com/problems/delete-node-in-a-bst/description/).

I wrote the following code:

// Example program
#include <iostream>
#include <string>

using namespace std;

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

TreeNode* findSmallest(TreeNode* root) {
        if(!root) return NULL;

        TreeNode* prev=root;
        while(root->left) {
            cout<<"Visiting: "<<root->val<<"\n";
            prev=root;
            root=root->left;
        }
        prev->left=NULL;

        cout<<"Returning: "<<root->val<<" and prev was: "<<prev->val<<"\n";
        return root;
    }

    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root) return NULL;

        if(root->val == key) {
            //This is the node to be deleted
            TreeNode* smallestOnRight = findSmallest(root->right);

            //the lines below do not actually change the root node - why?
            if(smallestOnRight) smallestOnRight->left=root->left;
            if(smallestOnRight) smallestOnRight->right=root->right;
            root=smallestOnRight;

            return root;
        }

        if(root->val>key)
            deleteNode(root->left, key);
        if(root->val<key)
            deleteNode(root->right, key);

        return root;
    }

int main()
{
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(3);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(6);
    root->left->right->left = new TreeNode(4);
    root->left->right->right = new TreeNode(7);

    root->right = new TreeNode(10);
    root->right->right = new TreeNode(14);
    root->right->right->left = new TreeNode(13);

    deleteNode(root, 3);

}

I am wondering why the lines below the comment do not actually change the root node. So, if the original tree was like (a), then after this process, the new tree is like (b), whereas it should have been like (c):

(a): Image (a)
(b): Image (b)
(c): Image (c)

So, basically only the node3 should be replaced with node4, but unfortunately this does not happen. Why is this so?

Edit: So the input would be:

[8,3,10,1,6,null,14,null,null,4,7,13,null]
3

(Tree is traversed in level order).

Edit: Here is the cpp.sh link: http://cpp.sh/9h2z

Upvotes: 0

Views: 65

Answers (1)

unxnut
unxnut

Reputation: 8839

You have not preserved node8 that should have been modified to point to node4. You need to preserve the parent of the node that is being deleted and modify the linkage in there.

Upvotes: 1

Related Questions