#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
// C++ program to implement optimized delete in BST.
using namespace std;
struct TreeNode {
int val, countOfLeftChild;
struct TreeNode *left, *right;
};
// A utility function to create a new BST node
TreeNode* newNode(int item)
{
TreeNode* temp = new TreeNode;
temp->val = item;
temp->countOfLeftChild = 0;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to do inorder traversal of BST
void inorder(TreeNode* root, bool printCountOfLeftChild)
{
if (root != NULL) {
inorder(root->left, printCountOfLeftChild);
if(printCountOfLeftChild)
printf("%d:%d ", root->val, root->countOfLeftChild);
else
printf("%d ", root->val);
inorder(root->right, printCountOfLeftChild);
}
}
/* A utility function to insert a new node with given key in BST */
TreeNode* insert(TreeNode* 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->val) {
node->left = insert(node->left, key);
node->countOfLeftChild++;
} else
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
/* Given a binary search tree and a key, this function
deletes the key and returns the new root */
TreeNode* deleteNode(TreeNode* root, int k)
{
// Base case
if (root == NULL)
return root;
// Recursive calls for ancestors of
// node to be deleted
if (root->val > k) {
root->left = deleteNode(root->left, k);
root->countOfLeftChild--;
return root;
}
else if (root->val < k) {
root->right = deleteNode(root->right, k);
return root;
}
// We reach here when root is the node
// to be deleted.
// If one of the children is empty
if (root->left == NULL) {
TreeNode* temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL) {
TreeNode* temp = root->left;
delete root;
return temp;
}
// If both children exist
else {
TreeNode* succParent = root;
// Find successor
TreeNode* succ = root->right;
while (succ->left != NULL) {
succParent = succ;
succ->countOfLeftChild--;
succ = succ->left;
}
// Delete successor. Since successor
// is always left child of its parent
// we can safely make successor's right
// right child as left of its parent.
// If there is no succ, then assign
// succ->right to succParent->right
if (succParent != root)
succParent->left = succ->right;
else
succParent->right = succ->right;
// Copy Successor Data to root
root->val = succ->val;
// Delete Successor and return root
delete succ;
return root;
}
}
void appendTree(TreeNode* root, vector<int>& result) {
if (root == nullptr) return;
appendTree(root->left, result);
result.push_back(root->val);
appendTree(root->right, result);
}
void getPage(TreeNode* root, vector<int>& result, int startIndex, int endIndex) {
if (root == nullptr || endIndex <= 0) return;
int countOfLeftChildPlusSelf = root->countOfLeftChild;
if (endIndex <= countOfLeftChildPlusSelf) { /* If endIndex is less than left child count. */
getPage(root->left, result, startIndex, endIndex);
}
else if (startIndex > 0) { /* if startIndex is not 0 then it is not including sub-tree from starting. */
if (countOfLeftChildPlusSelf < startIndex) { /* reject the left subtree if left child cound is less than startIndex */
getPage(root->right, result, startIndex - countOfLeftChildPlusSelf - 1, endIndex - countOfLeftChildPlusSelf - 1);
}
else {
getPage(root->left, result, startIndex, countOfLeftChildPlusSelf);
result.push_back(root->val);
vector<int> rightPart;
getPage(root->right, rightPart, 0, endIndex - countOfLeftChildPlusSelf - 1);
for (int val : rightPart) result.push_back(val);
}
}
else { /* if startIndex is 0 and endIndex is less than child count then it is including sub-tree from starting to endIndex. */
appendTree(root->left, result);
result.push_back(root->val);
getPage(root->right, result, startIndex, endIndex - countOfLeftChildPlusSelf - 1);
}
}
inline int getMaximunNumberOfPages(int size, int elementsPerPage) {
return (int)ceil(size / ((elementsPerPage) * 1.0f));
}
vector<int> getPage(TreeNode* root, int size, int pageNumber, int elementsPerPage) {
vector<int> result;
if (root == nullptr || elementsPerPage <= 0) return result;
int numberofPages = getMaximunNumberOfPages(size, elementsPerPage);
if (pageNumber > numberofPages || pageNumber < 1) return result;
int startIndex = (pageNumber - 1) * elementsPerPage;
int endIndex = min(size, startIndex + elementsPerPage);
getPage(root, result, startIndex, endIndex);
return result;
}
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ \ /
35 45 65 75 */
TreeNode* root = NULL;
vector<int> nodeVals = {50, 30, 20, 40, 35, 45, 70, 60, 80, 65, 75};
for(int val: nodeVals) {
printf("\nInserting %d\n", val);
root = insert(root, val);
printf("Inorder traversal of the modified tree \n");
inorder(root, true);
printf("\n");
}
cout << endl;
inorder(root, false);
cout << endl;
vector<int> result;
int maxPages, elementsPerPage, pageNumber;
/* Test cases */
for (elementsPerPage = 1; elementsPerPage <= nodeVals.size(); elementsPerPage++) {
cout << "ElementPerPage: " << elementsPerPage << endl;
maxPages = getMaximunNumberOfPages(nodeVals.size(), elementsPerPage);
for (pageNumber = 1; pageNumber <= maxPages; pageNumber++) {
cout << "\tPageNumber: " << pageNumber << " Val: ";
result = getPage(root, nodeVals.size(), pageNumber, elementsPerPage);
for (int val : result) {
printf("%d ", val);
}
cout << endl;
}
}
/* Test cases, when elementPerPage is more than tree*/
elementsPerPage = nodeVals.size() + 1;
cout << "ElementPerPage: " << elementsPerPage << endl;
maxPages = getMaximunNumberOfPages(nodeVals.size(), elementsPerPage);
for (pageNumber = 1; pageNumber <= maxPages; pageNumber++) {
cout << "\tPageNumber: " << pageNumber << " Val: ";
result = getPage(root, nodeVals.size(), pageNumber, elementsPerPage);
for (int val : result) {
printf("%d ", val);
}
cout << endl;
}
/* Test cases, when pageNumber is not present*/
elementsPerPage = 5;
cout << "ElementPerPage: " << elementsPerPage << endl;
maxPages = getMaximunNumberOfPages(nodeVals.size(), elementsPerPage);
pageNumber = maxPages + 1;
cout << "\tPageNumber: " << pageNumber << " Val: ";
result = getPage(root, nodeVals.size(), pageNumber, elementsPerPage);
for (int val : result) {
printf("%d ", val);
}
cout << endl;
for(int val: nodeVals) {
printf("\nDeleting %d\n", val);
root = deleteNode(root, val);
printf("Inorder traversal of the modified tree \n");
inorder(root, true);
printf("\n");
}
return 0;
}
