C++ Program Of Binary Tree Sorting

In this article, you will learn how binary trees can be leveraged for sorting, focusing on the fundamental concept of a Binary Search Tree (BST) to achieve an ordered sequence of elements. We will explore the principles behind this method and provide a practical C++ implementation.

Problem Statement

Sorting data is a ubiquitous task in computer science, essential for efficient searching, merging, and data presentation. While array-based sorting algorithms like QuickSort or MergeSort are highly effective for static datasets, dynamic scenarios—where elements are frequently inserted or deleted—can pose challenges. Re-sorting an entire array or maintaining order through insertions often involves costly element shifting, leading to decreased performance. The problem is to find a sorting mechanism that efficiently handles dynamic data while maintaining an ordered structure.

Example

Consider an unsorted list of numbers: [50, 30, 70, 20, 40, 60, 80]. A binary tree sort would process these numbers by inserting them into a tree structure, maintaining a specific order. Once all elements are inserted, traversing the tree in a specific way will yield the sorted output: [20, 30, 40, 50, 60, 70, 80].

Background & Knowledge Prerequisites

To understand binary tree sorting, a basic grasp of the following concepts is essential:

• C++ Basics: Variables, data types, functions, control flow statements.
• Pointers: Understanding how pointers work for dynamic memory allocation and linking nodes.
• Structs/Classes: Defining custom data structures for tree nodes.
• Recursion: Many tree operations are naturally recursive.
• Basic Tree Concepts: What a node is, root, left child, right child, parent, leaf.
• Binary Search Tree (BST) Properties: For any given node, all values in its left subtree are smaller, and all values in its right subtree are larger.

Use Cases or Case Studies

Binary tree sorting proves particularly useful in several practical scenarios:

• Dynamic Data Management: When data arrives continuously and needs to be kept sorted without constant re-sorting of an entire array.
• Database Indexing: B-trees (a generalization of BSTs) are extensively used in database systems to index records, allowing for efficient retrieval and sorting of data.
• Symbol Tables: Compilers and interpreters use symbol tables to store information about variables, functions, etc., often structured as trees for quick lookups and ordered iteration.
• Priority Queues: Although typically implemented with heaps, a self-balancing BST can also serve as an effective priority queue, allowing elements to be extracted in sorted order.
• Real-time Data Processing: Systems that need to process and maintain sorted lists of events or measurements as they occur.

Solution Approaches

The most common and fundamental approach to binary tree sorting involves using a Binary Search Tree (BST).

Binary Search Tree (BST) Sort

This approach involves two main steps: first, constructing a Binary Search Tree by inserting all elements from the unsorted list, and second, performing an in-order traversal of the constructed BST. Due to the inherent properties of a BST, an in-order traversal always visits nodes in ascending order, effectively sorting the elements.

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

Run

Sample Output:

Original array: 50 30 70 20 40 60 80 
Sorted array (using BST in-order traversal): 20 30 40 50 60 70 80

Stepwise Explanation for BST Sort:

1. Node Structure Definition: A Node struct is defined, containing an integer data value and two pointers (left and right) to its child nodes. A constructor simplifies node creation.
2. Insertion (insert function): This recursive function adds new elements to the BST.

• If the tree (or subtree) is empty, a new node is created and returned as the root of that subtree.
• If the new data is less than the current node's data, it's inserted into the left subtree.
• If the new data is greater, it's inserted into the right subtree.
• Duplicate values are typically handled by either ignoring them or placing them in the right subtree.

1. In-order Traversal (inorderTraversal function): This recursive function is crucial for sorting.

• It first recursively traverses the left subtree.
• Then, it visits (prints) the data of the current node.
• Finally, it recursively traverses the right subtree.
• Due to BST properties, this sequence guarantees visiting nodes in ascending order of their data values.

1. Memory Cleanup (deleteTree function): A recursive function to deallocate all dynamically created nodes to prevent memory leaks.
2. Main Function Logic:

• An unsorted_array is initialized.
• An empty root pointer is set for the BST.
• Each element from the unsorted_array is iteratively inserted into the BST using the insert function.
• After all elements are inserted, the inorderTraversal function is called with the root to print the elements in sorted order.
• Finally, deleteTree is called to free memory.

Conclusion

Binary tree sorting, particularly using a Binary Search Tree, provides an intuitive and efficient method for ordering data, especially when dealing with dynamic collections. The core idea is to leverage the BST's property of maintaining order during insertion, allowing for an in-order traversal to yield a sorted sequence. While its average-case time complexity for building the tree and traversal is O(N log N), similar to comparison sorts, its worst-case scenario can degrade to O(N^2) if the tree becomes skewed (like a linked list). This can be mitigated by using self-balancing BSTs like AVL trees or Red-Black trees.

Summary

• Binary Tree Sorting: Uses tree structures, primarily Binary Search Trees (BSTs), to sort elements.
• Process: Elements are inserted into the BST one by one, maintaining BST properties.
• Sorting Step: An in-order traversal of the BST yields elements in ascending order.
• Advantages: Efficient for dynamic datasets where elements are frequently added or removed.
• Time Complexity: O(N log N) on average for building and traversing, O(N^2) in worst-case (skewed tree).
• Mitigation: Self-balancing BSTs prevent worst-case scenarios, ensuring O(N log N) performance consistently.