Leetcode 450 Solution

This article provides solution to leetcode question 450 (delete-node-in-a-bst)
Categories:
Tags:
Access this page by simply typing in "lcs 450" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/delete-node-in-a-bst

Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == NULL)
            return NULL;
        else if (root->val > key)
        {
            root->left = deleteNode(root->left, key);
            return root;
        }
        else if (root->val < key)
        {
            root->right = deleteNode(root->right, key);
            return root;
        }
        else
        {
            if (root->left == NULL)
                return root->right;
            else if (root->right == NULL)
                return root->left;

            root->val = findMin(root->right);
            root->right = deleteNode(root->right, root->val);
            return root;
        }
    }

    int findMin(TreeNode* root)
    {
        TreeNode* p = root;
        while (p->left != NULL)
            p = p->left;

        return p->val;
    }
};