Implement below operations on Binary Search Tree
- Insert Operation
- Find Min
- Find Max
- In-order Traversal
- Pre-order Traversal
- Post-order Traversal
- Get height of the tree
- Check if the tree is a balanced tree
- Delete node with given key
- Find given key
Solution in C++
#include<iostream> #include<vector> #include<string> using namespace std; struct Node { int data; Node *left; Node *right; }; //global root declaration Node *root; Node* insert(int num, Node* root) { if(root == NULL) { root = new Node; root->data = num; root->left = root->right = NULL; } else if(num < root->data) root->left = insert(num, root->left); else if(num > root->data) root->right = insert(num, root->right); return root; } Node* findMax(Node* root) { if(root == NULL) return NULL; else if(root->right == NULL) return root; else return findMax(root->right); } Node* findMin(Node* root) { if(root == NULL) return NULL; else if(root->left == NULL) return root; else return findMin(root->left); } void inorder(Node *root) { if(root == NULL) return; inorder(root->left); cout << root->data << " "; inorder(root->right); } void preOrder(Node *root) { if (!root) return; cout << root->data << " "; preOrder(root->left); preOrder(root->right); } void postOrder(Node *root) { if (!root) return; postOrder(root->left); postOrder(root->right); cout << root->data << " "; } int getHeight(Node *root) { if (!root) return 0; return 1 + max(getHeight(root->left) , getHeight(root->right)); } bool isBalanced(Node *root) { if (!root) return false; int leftHeight = getHeight(root->left); int rightHeight = getHeight(root->right); if (abs(leftHeight - rightHeight) > 1) return false; return true; } Node* makeEmpty(Node *root) { if(root == NULL) return NULL; { makeEmpty(root->left); makeEmpty(root->right); delete root; } return NULL; } Node* remove(Node* node, int key) { Node* temp; if(node == NULL) return NULL; else if(key < node->data) node->left = remove(node->left, key); else if(key > node->data) node->right = remove(node->right, key); else if(node->left && node->right) { temp = findMin(node->right); node->data = temp->data; node->right = remove(node->right, node->data); } else { temp = node; if(node->left == NULL) node = node->right; else if(node->right == NULL) node = node->left; delete temp; } return node; } Node* find(Node *root, int key) { if(root == NULL) return NULL; else if(key < root->data) return find(root->left, key); else if(key > root->data) return find(root->right, key); else return root; } int main() { root = insert(10, root); root = insert(30, root); root = insert(20, root); root = insert(50, root); root = insert(60, root); root = insert(25, root); root = insert(15, root); cout<<"\nThe values displayed using inorder traversal = "<<endl; inorder(root); cout<<"\nThe values displayed using preOrder traversal = "<<endl; preOrder(root); cout<<"\nThe values displayed using postOrder traversal = "<<endl; postOrder(root); Node *max_value = findMax(root); cout<<"\n\nThe maximum value is "<< max_value->data <<endl; Node *min_value = findMin(root); cout<<"\nThe minumim value is "<< min_value->data <<endl; cout<<"\nThe height of the tree is = "<< getHeight(root)<<endl; if(isBalanced(root)) cout<<"\nThe tree is balanced"<<endl; else cout<<"\nThe tree not is balanced"<<endl; int key = 60; if(find(root, key) != NULL) cout<<"\nThe key "<<key<<" is present\n"<<endl; else cout<<"\nThe key "<<key<<" is not present\n"<<endl; remove(root, key); cout<<"\nThe key "<<key<<" has been deleted"<<endl; cout<<"\nThe values displayed using inorder traversal = "<<endl; inorder(root); cout<<endl; return 0; }
Output:
The values displayed using inorder traversal = 10 15 20 25 30 50 60 The values displayed using preOrder traversal = 10 30 20 15 25 50 60 The values displayed using postOrder traversal = 15 25 20 60 50 30 10 The maximum value is 60 The minumim value is 10 The height of the tree is = 4 The tree not is balanced The key 60 is present The key 60 has been deleted The values displayed using inorder traversal = 10 15 20 25 30 50
Further Reading:
selvabharathi
void inorder(Node *root)
{
if(root == NULL)
return; // what does it return, can you please //explain me the iteration in brief.
inorder(root->left);
cout <data <right);
}
prodevelopertutorial
It will just return to the calling function, without any values.