Binary Search Tree to do user add and rank query


  • 0
    F

    Kth Largest Elements in unsorted array

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            int left = 0, right = nums.size() - 1;
            while (true) {
                int pos = k_element(nums, left, right);
                if (pos == k-1) return nums[pos];
                if (pos > k-1) right = pos - 1;
                else left = pos + 1;
            }
        }
        
        int k_element(vector<int>& nums, int left, int right) {
            //move all the bigger element left & move all the smaller element right
            int pivot = nums[left];
            int l = left + 1, r = right;
            while (l <= r) {
                if (nums[l] < pivot && nums[r] > pivot)
                    swap(nums[l++], nums[r--]);
                if (nums[l] >= pivot) l++;
                if (nums[r] <= pivot) r--;
            }
            swap(nums[left], nums[r]);
            return r;
        }
    };
    

    Kth Smallest Elements in BST

    class Solution {
    public:
        int kthSmallest(TreeNode* root, int k) {
            stack<TreeNode*> st;
            while(root != nullptr) {
                st.push(root);
                root = root->left;
            }
            while (k != 0) {
                TreeNode* cur = st.top();
                st.pop();
                k --;
                if (k == 0)  return cur->val;
                TreeNode* right = cur->right;
                while (right != nullptr) {
                    st.push(right);
                    right = right->left;
                }
            }
            return -1;
        }
    };
    

    Here are the Binary Search Tree insert & delete implementation

    // C function to search a given key in a given BST
    struct node* search(struct node* root, int key)
    {
        // Base Cases: root is null or key is present at root
        if (root == NULL || root->key == key)
           return root;
        
        // Key is greater than root's key
        if (root->key < key)
           return search(root->right, key);
     
        // Key is smaller than root's key
        return search(root->left, key);
    }
    
    struct node* insert(struct node* node, int key)
    {
        /* If the tree is empty, return a new node */
        if (node == NULL) return newNode(key);
     
        /* Otherwise, recur down the tree */
        if (key < node->key)
            node->left  = insert(node->left, key);
        else if (key > node->key)
            node->right = insert(node->right, key);   
     
        /* return the (unchanged) node pointer */
        return node;
    }
    
    struct node * minValueNode(struct node* node)
    {
        struct node* current = node;
     
        /* loop down to find the leftmost leaf */
        while (current->left != NULL)
            current = current->left;
     
        return current;
    }
    
    struct node* deleteNode(struct node* root, int key)
    {
        // base case
        if (root == NULL) return root;
     
        // If the key to be deleted is smaller than the root's key,
        // then it lies in left subtree
        if (key < root->key)
            root->left = deleteNode(root->left, key);
     
        // If the key to be deleted is greater than the root's key,
        // then it lies in right subtree
        else if (key > root->key)
            root->right = deleteNode(root->right, key);
     
        // if key is same as root's key, then This is the node
        // to be deleted
        else
        {
            // node with only one child or no child
            if (root->left == NULL)
            {
                struct node *temp = root->right;
                free(root);
                return temp;
            }
            else if (root->right == NULL)
            {
                struct node *temp = root->left;
                free(root);
                return temp;
            }
     
            // node with two children: Get the inorder successor (smallest
            // in the right subtree)
            struct node* temp = minValueNode(root->right);
     
            // Copy the inorder successor's content to this node
            root->key = temp->key;
     
            // Delete the inorder successor
            root->right = deleteNode(root->right, temp->key);
        }
        return root;
    }
    

  • 0
    F
    class Solution {
    public:
        int kthSmallest(TreeNode* root, int k) {
            stack<TreeNode*> st;
            TreeNode* p = root;
            while(p) {
                st.push(p);
                p = p->left;
            }
            while(!st.empty()) {
                TreeNode* cur = st.top();
                st.pop();
                k--;
                if (k == 0) return cur->val;
                if (cur->right) {
                    TreeNode* r = cur->right;
                    while(r) {
                        st.push(r);
                        r = r->left;
                    }
                }
            }
            return -1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.