fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node {
  5.     int val;
  6.     Node* left;
  7.     Node* right;
  8.  
  9.     Node(int x) {
  10.         val = x;
  11.         left = NULL;
  12.         right = NULL;
  13.     }
  14. };
  15.  
  16. Node* insert(Node* root, int x) {
  17.     if (root == NULL) {
  18.         root = new Node(x);
  19.     } else if (x < root->val) {
  20.         root->left = insert(root->left, x);
  21.     } else {
  22.         root->right = insert(root->right, x);
  23.     }
  24.     return root;
  25. }
  26.  
  27. void preorder(Node* root) {
  28.     if(root == NULL) return;
  29.  
  30.     cout << root->val << " ";
  31.     preorder(root->left);
  32.     preorder(root->right);
  33. }
  34.  
  35. void inorder(Node* root) {
  36.     if(root == NULL) return;
  37.  
  38.     inorder(root->left);
  39.     cout << root->val << " ";
  40.     inorder(root->right);
  41. }
  42.  
  43. void postorder(Node* root) {
  44.     if(root == NULL) return;
  45.  
  46.     postorder(root->left);
  47.     postorder(root->right);
  48.     cout << root->val << " ";
  49. }
  50.  
  51. Node* findMin(Node* root) {
  52.     while (root->left != NULL) {
  53.         root = root->left;
  54.     }
  55.     return root;
  56. }
  57.  
  58. Node* deleteNode(Node* root, int val) {
  59.     if (root == NULL) {
  60.         return root;
  61.     }
  62.     if (val < root->val) {
  63.         root->left = deleteNode(root->left, val);
  64.     } else if (val > root->val) {
  65.         root->right = deleteNode(root->right, val);
  66.     } else {
  67.         // Node found
  68.         if (root->left == NULL) {
  69.             // Node with only right child or no child
  70.             Node* temp = root->right;
  71.             delete root; // delete current node
  72.             return temp; // replace current node by right child
  73.         } else if (root->right == NULL) {
  74.             // Node with only left child or no child
  75.             Node* temp = root->left;
  76.             delete root; // delete current node
  77.             return temp; // replace current node by left child
  78.         } else {
  79.             // Node with two children
  80.             Node* temp = findMin(root->right);  // Find the inorder successor
  81.             root->val = temp->val;  // Copy the inorder successor's value to the node
  82.             root->right = deleteNode(root->right, temp->val);  // Delete the inorder successor
  83.         }
  84.     }
  85.     return root;
  86. }
  87.  
  88. bool find(Node* root, int val) {
  89.     if (root == NULL) {
  90.         return 0; // Value not found
  91.     }
  92.     if (root->val == val) {
  93.         return 1; // Value found
  94.     } else if (val < root->val) {
  95.         return find(root->left, val);
  96.     } else {
  97.         return find(root->right, val);
  98.     }
  99. }
  100.  
  101. int main() {
  102.     ios_base::sync_with_stdio(0); cin.tie(0);
  103.     Node* root = NULL;
  104.  
  105.     // Insert elements into BST
  106.     root = insert(root, 5);
  107.     root = insert(root, 3);
  108.     root = insert(root, 7);
  109.     root = insert(root, 2);
  110.     root = insert(root, 4);
  111.     root = insert(root, 6);
  112.     root = insert(root, 8);
  113.  
  114.     // Print elements of BST in sorted order
  115.     cout << "Inorder traversal of BST: ";
  116.     inorder(root);
  117.     cout << "\n";
  118.  
  119.     // Find elements in BST
  120.     cout << "Find 3 in BST: " << find(root, 3) << endl; // Output should be 1
  121.     cout << "Find 9 in BST: " << find(root, 9) << endl; // Output should be 0
  122.  
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder traversal of BST: 2 3 4 5 6 7 8 
Find 3 in BST: 1
Find 9 in BST: 0
https://ideone.com/5svBEb
language:
C++ (gcc 8.3)
created:
126 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!