Example: Binary Search Tree Sorting in C++

// 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;
}