Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- using namespace std;
- struct BSTNode {
- int data;
- BSTNode* left;
- BSTNode* right;
- BSTNode(int value) {
- data = value;
- left = nullptr;
- right = nullptr;
- }
- };
- BSTNode* insert(BSTNode* root, int key) {
- if (root == nullptr) {
- return new BSTNode(key);
- }
- if (root->data > key) root->left = insert(root->left, key);
- if (root->data < key) root-> right = insert(root -> right, key);
- return root;
- }
- BSTNode* minVal(BSTNode* root) {
- BSTNode* tmp = root;
- while (tmp != nullptr&&tmp->left != nullptr) tmp = tmp->left;
- return tmp;
- }
- BSTNode* maxVal(BSTNode* root) {
- BSTNode* tmp = root;
- while (tmp != nullptr&&tmp->right != nullptr) tmp = tmp->right;
- return tmp;
- }
- int wayLength(BSTNode* root,int key) {
- int wayLength = 0;
- while (root != nullptr) {
- if (root->data == key) return wayLength;
- else if (root->data < key) root = root->right;
- else root = root->left;
- wayLength++;
- }
- return -1;
- }
- void inOrder(BSTNode* root) {
- if (root != nullptr) {
- inOrder(root->left);
- cout << root->data << " ";
- inOrder(root->right);
- }
- return;
- }
- BSTNode* deleteNode(BSTNode* root, int key) {
- if (root == nullptr) return nullptr;
- if (root->data > key) root->left = deleteNode(root->left, key);
- else if (root->data < key) root->right = deleteNode(root->right, key);
- else {
- if (root->left == nullptr) {
- BSTNode* tmp = root->right;
- delete root;
- return tmp;
- }
- else if (root->right == nullptr) {
- BSTNode* tmp = root->left;
- delete root;
- return tmp;
- }
- BSTNode* tmp = minVal(root->right);
- root->data = tmp->data;
- root->right = deleteNode(root->right, tmp->data);
- }
- return root;//This is needed when trying to delete a node that does not exsist
- }
- int countLeftNodes(BSTNode* root) {
- if (root == nullptr || root->left == nullptr) return 0;
- if (root->right == nullptr) return 1 + countLeftNodes(root->left);
- return 1 + countLeftNodes(root->left) + countLeftNodes(root->right);
- }
- int countRightNodes(BSTNode* root) {
- if (root == nullptr || root->right == nullptr) return 0;
- if (root->left == nullptr) return 1 + countRightNodes(root->right);
- return 1 + countRightNodes(root->left) + countRightNodes(root->right);
- }
- void leftRight(BSTNode* root) {
- cout << "[" << countLeftNodes(root) << "," << countRightNodes(root) << "]\n";
- }
- void levelOrderTraversal(BSTNode* root) {
- if (root!=nullptr) {
- queue <BSTNode*> q;
- q.push(root);
- while (!q.empty()) {
- BSTNode* node = q.front();
- q.pop();
- cout << node->data << " ";
- if (node->left!=nullptr) q.push(node->left);
- if (node->right != nullptr) q.push(node->right);
- }
- }
- }
- bool checkBST(BSTNode* root, BSTNode* l = nullptr, BSTNode* r = nullptr) {
- if (root == nullptr) return true;
- if ((l != nullptr&&root->data <= l->data)
- ||
- (r != nullptr&&root->data >= r->data)) return false;
- return checkBST(root->left, l, root)
- &&
- checkBST(root->right, root, r);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement