C++ Online Compiler
Example: Binary Search Tree Sorting in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// Binary Search Tree Sorting #include <iostream> #include <vector> #include <algorithm> // Required for std::for_each (optional, for printing) using namespace std; // Step 1: Define the structure for a tree node struct Node { int data; Node* left; Node* right; // Constructor to create a new node Node(int val) : data(val), left(nullptr), right(nullptr) {} }; // Step 2: Function to insert a new value into the BST Node* insert(Node* root, int data) { // If the tree is empty, create a new node and return it as the root if (root == nullptr) { return new Node(data); } // Otherwise, recur down the tree if (data < root->data) { root->left = insert(root->left, data); } else if (data > root->data) { root->right = insert(root->right, data); } // If data is equal, we usually don't insert duplicates or handle as per requirement. // For sorting, we can ignore duplicates or allow them to go right. return root; } // Step 3: Function to perform an in-order traversal and print elements void inorderTraversal(Node* root) { if (root != nullptr) { inorderTraversal(root->left); // Traverse left subtree cout << root->data << " "; // Visit current node inorderTraversal(root->right); // Traverse right subtree } } // Step 4: Function to free up memory allocated for the tree nodes void deleteTree(Node* root) { if (root != nullptr) { deleteTree(root->left); deleteTree(root->right); delete root; } } int main() { // Original unsorted array vector<int> unsorted_array = {50, 30, 70, 20, 40, 60, 80}; cout << "Original array: "; for (int x : unsorted_array) { cout << x << " "; } cout << endl; Node* root = nullptr; // Initialize an empty BST // Step 5: Insert all elements from the array into the BST for (int data : unsorted_array) { root = insert(root, data); } cout << "Sorted array (using BST in-order traversal): "; // Step 6: Perform in-order traversal to get sorted elements inorderTraversal(root); cout << endl; // Clean up memory deleteTree(root); return 0; }
Output
Clear
ADVERTISEMENTS