online compiler and debugger for c/c++

#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; }