# Binary Search Tree to do user add and rank query

• 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;
}
``````

• ``````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;
}
};
``````

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