Implement below operations on Binary 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 entire tree
- Find given key
Solution in C++
#include<iostream> #include<vector> #include<string> #include<queue> using namespace std; struct Node { int data; Node *left; Node *right; Node(int x) { data = x; left = NULL; right = NULL; } }; //global root declaration Node *root; 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 iterativeSearch(Node *root, int key) { // Base Case if (root == NULL) return false; // Create an empty queue for level order traversal queue<Node *> q; // Enqueue Root and initialize height q.push(root); // Queue based level order traversal while (q.empty() == false) { // See if current node is same as key Node *node = q.front(); if (node->data == key) return true; // Remove current node and enqueue its children q.pop(); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); } return false; } int findMax(Node* root) { // Base case if (root == NULL) return INT_MIN; int result = root->data; // Find the maximum value in left sub-tree int lres = findMax(root->left); // Find the maximum value in right sub-tree int rres = findMax(root->right); if (lres > result) result = lres; if (rres > result) result = rres; return result; } int findMin(Node* root) { // Base case if (root == NULL) return INT_MAX; int result = root->data; // Find the maximum value in left sub-tree int lres = findMin(root->left); // Find the maximum value in right sub-tree int rres = findMin(root->right); if (lres < result) result = lres; if (rres < result) result = rres; return result; } 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; } void deleteTree(Node* node) { if (node == NULL) return; /* first delete both subtrees */ deleteTree(node->left); deleteTree(node->right); /* then delete the node */ cout<<"\n Deleting node = "<<node->data<<endl; free(node); } int main() { root = new Node(1); /* 1 */ root -> left = new Node(2); root -> right = new Node(3); /* 1 / \ 2 3 */ root -> left -> left = new Node(4); /* 1 / \ 2 3 / 4 */ root -> left -> right = new Node(8); root -> left -> right -> right = new Node(5); root -> left -> right -> left = new Node(6); root -> left -> left -> right = new Node(15); root -> left -> left -> left = new Node(16); 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); int maxValue = findMax(root); cout<<"\n\nThe maximum value is "<< maxValue <<endl; int minValue = findMin(root); cout<<"\nThe minumim value is "<< minValue <<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 = 16; if(iterativeSearch(root, key)) cout<<"\nThe key "<<key<<" is present\n"<<endl; else cout<<"\nThe key "<<key<<" is not present\n"<<endl; cout<<"Deleting entire tree"<<endl; deleteTree(root); }
Output:
The values displayed using inorder traversal = 16 4 15 2 6 8 5 1 3 The values displayed using preOrder traversal = 1 2 4 16 15 8 6 5 3 The values displayed using postOrder traversal = 16 15 4 6 5 8 2 3 1 The maximum value is 16 The minumim value is 1 The height of the tree is = 4 The tree not is balanced The key 16 is present Deleting entire tree Deleting node = 16 Deleting node = 15 Deleting node = 4 Deleting node = 6 Deleting node = 5 Deleting node = 8 Deleting node = 2 Deleting node = 3 Deleting node = 1
Further Reading: