Remove Node in Binary Search Tree

Description

Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

Example
Given binary search tree:
    5
   / \
  3   6
 / \
2   4
Remove 3, you can either return:
    5
   / \
  2   6
   \
    4
or
    5
   / \
  4   6
 /
2

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    TreeNode* removeNode(TreeNode* root, int value) {
        // write your code here
        // Test Case : {10,5,15,3,8,12,18,2,4,7,9,11,13,16,19}, 15
        //             {2}, 2
        if (!root) {
            return nullptr;
        }
        TreeNode dummy(-1);
        dummy.left = root;
        // divide by value to find prev and target node
        TreeNode* parent = findnode(&dummy, root ,value);
        TreeNode* cur = nullptr;
        if (parent->left && parent->left->val == value) {
            cur = parent->left;
        } else if (parent->right && parent->right->val == value) {
            cur = parent->right;
        } else {
            return dummy.left;
        }
        // process rest sift up
        deletenode(parent, cur);
        return dummy.left;
    }
    TreeNode* findnode(TreeNode* parent, TreeNode* root, int value) {
        // inorder traversal : dfs cannot find prev
        // divide by root : finding left or right and record prev
        TreeNode* prev = nullptr;
        while (root) {
            TreeNode* tmp = root;
            if (root->val < value) {
                root = root->right;
            } else if (root->val > value) {
                root = root->left;
            } else {
                break;
            }
            prev = tmp;
        }
        if (!prev) {
            return parent; 
        } else {
            return prev;
        }
    }
    void deletenode(TreeNode* parent, TreeNode* node) {
        // node no right
        if (!node->right) {
            if (parent->left == node) {
            // node on the left
            // Example:  
            //     5
            //   3   <- remove
            // 1
            //   2
            // ------> 
            //     5    
            //  1    6
            //    2  
                parent->left = node->left;
            } else {
            // node on the right
            // Example
            //     5
            //   3   8 <- remove
            //      7
            //       10
            // ------->
            //     5    
            //   3   7
            //        10
                parent->right = node->left;
            }
        } else {
        // node has right
            // -------------------------------------------------------------
            // // Raw Version
            // // node on left
            // if (parent->left == node) {
            //     parent->left = node->right;
            //     // node left to after the node->right's final left
            //     TreeNode* nodeleft = node->left;
            //     TreeNode* cur = node->right;
            //     while (cur->left) {
            //         cur = cur->left;
            //     }
            //     cur->left = nodeleft;
            //     delete node;
            // } else {
            // // node on right
            //     parent->right = node->right;
            //     // node left to after the node->right's final left
            //     TreeNode* nodeleft = node->left;
            //     TreeNode* cur = node->right;
            //     while (cur->left) {
            //         cur = cur->left;
            //     }
            //     cur->left = nodeleft;
            //     delete node;
            // }
            // ------------------------------------
            // Simplified Version
            TreeNode* nodeleft = node->left;
            TreeNode* cur = node->right;
            while (cur->left) {
                cur = cur->left;
            }
            cur->left = nodeleft;
            if (parent->left == node) {
                parent->left = node->right;
            } else {
                parent->right = node->right;
            }
        }
        return;
    }
};

Similar problems

x

Tags

x