C Program Of Binary Tree Sorting

Binary tree sorting is a sorting technique that leverages the properties of a Binary Search Tree (BST) to arrange elements in order. In this article, you will learn how to implement binary tree sorting using C, specifically focusing on the construction of a BST and its inorder traversal for sorting.

Problem Statement

Sorting a collection of data is a fundamental task in computer science, crucial for efficient searching, merging, and database operations. The challenge is to efficiently arrange an unordered list of elements into a specific order (ascending or descending) while potentially illustrating a data structure's role in this process.

Example

Imagine you have a list of numbers: [50, 30, 70, 20, 40, 60, 80]. When sorted using a binary search tree, these numbers would be inserted into the tree, and an inorder traversal would yield the sorted sequence: 20, 30, 40, 50, 60, 70, 80.

Background & Knowledge Prerequisites

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

• C Language Basics: Variables, data types, functions, control structures (if, loops).
• Pointers: Understanding how to declare, initialize, and use pointers to manage memory addresses.
• Structs: Defining custom data types to group related data.
• Recursion: Functions calling themselves, which is fundamental for tree traversals.
• Binary Trees: Basic concepts of nodes, root, children, and leaves.
• Binary Search Trees (BSTs): Understanding that for any given node, all values in its left subtree are smaller, and all values in its right subtree are larger.
• Tree Traversal: Specifically, inorder traversal (Left -> Root -> Right) which visits nodes in ascending order for a BST.

Use Cases

Binary tree sorting is more conceptual for general-purpose sorting due to potential performance issues with unbalanced trees, but the underlying BST structure has many practical applications:

• Symbol Tables/Dictionaries: Efficiently storing and retrieving key-value pairs where keys need to be ordered.
• Database Indexing: Creating indexes on columns to speed up data retrieval operations based on value ranges.
• Expression Parsers: Representing arithmetic or logical expressions where operator precedence and operand relationships are crucial.
• Game Development: Managing game objects or entities that need to be efficiently accessed or updated based on certain attributes (e.g., spatial partitioning using k-d trees, a type of binary tree).
• Data Validation and Uniqueness Checks: Quickly determining if an element already exists in a collection.

Solution Approaches

The primary approach for binary tree sorting involves two main steps: constructing a Binary Search Tree (BST) from the given elements and then performing an inorder traversal of the BST.

Approach 1: Building a BST and Inorder Traversal

This approach involves creating a node structure for the tree, a function to insert new elements while maintaining BST properties, and a function to traverse the tree in inorder fashion to print the sorted elements.

One-line summary

Build a Binary Search Tree by inserting elements, then traverse it in inorder to retrieve them in sorted order.

Code example

// Binary Tree Sorting
#include <stdio.h>
#include <stdlib.h> // Required for malloc

// Define the structure for a tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to insert a node into the BST
struct Node* insert(struct Node* root, int value) {
    // If the tree is empty, return a new node
    if (root == NULL) {
        return createNode(value);
    }

    // Otherwise, recur down the tree
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    // If value is equal, do not insert duplicates (or handle as per requirement)
    return root;
}

// Function to perform inorder traversal of the BST (Left-Root-Right)
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);  // Traverse left subtree
        printf("%d ", root->data);     // Visit root node
        inorderTraversal(root->right); // Traverse right subtree
    }
}

// Function to free the memory allocated for the tree
void freeTree(struct Node* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

int main() {
    // Step 1: Initialize an empty BST
    struct Node* root = NULL;

    // Step 2: Define an array of unsorted numbers
    int arr[] = {50, 30, 70, 20, 40, 60, 80};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 3: Insert each element from the array into the BST
    printf("Original array elements: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
        root = insert(root, arr[i]);
    }
    printf("\\n");

    // Step 4: Perform inorder traversal to get sorted elements
    printf("Sorted elements (Inorder Traversal): ");
    inorderTraversal(root);
    printf("\\n");

    // Step 5: Free allocated memory
    freeTree(root);

    return 0;
}

Run

Sample output

Original array elements: 50 30 70 20 40 60 80 
Sorted elements (Inorder Traversal): 20 30 40 50 60 70 80

Stepwise explanation

1. Define Node Structure: A struct Node is created with an integer data field and two pointers, left and right, for its children.
2. createNode Function: This helper function allocates memory for a new node, initializes its data with the given value, and sets its left and right children pointers to NULL.
3. insert Function:

• This is a recursive function that takes the current root of a subtree and the value to be inserted.
• If the root is NULL (meaning an empty tree or an empty spot for insertion), it creates and returns a new node with the value.
• If the value is less than the current root->data, it recursively calls insert on the root->left subtree.
• If the value is greater than the current root->data, it recursively calls insert on the root->right subtree.
• Duplicate values are typically ignored or handled differently based on requirements; in this example, they are effectively ignored by the if-else if structure.

1. inorderTraversal Function:

• This is another recursive function.
• It first recursively calls itself on the root->left subtree. This ensures all smaller elements are processed first.
• Then, it prints the root->data.
• Finally, it recursively calls itself on the root->right subtree to process larger elements.
• This sequence (Left -> Root -> Right) naturally visits nodes in ascending order for a BST.

1. freeTree Function: A crucial function to deallocate all memory used by the tree nodes to prevent memory leaks. It recursively frees child nodes before freeing the parent.
2. main Function:

• Initializes an empty root pointer.
• Defines an arr of unsorted integers.
• Iterates through the arr, inserting each element into the BST using the insert function.
• Calls inorderTraversal with the root to print the sorted elements.
• Calls freeTree to clean up memory.

Conclusion

Binary tree sorting provides a clear illustration of how a specific data structure, the Binary Search Tree, can be used to sort data. By inserting elements into a BST and then performing an inorder traversal, elements are naturally retrieved in sorted order. While not the most efficient general-purpose sorting algorithm due to its O(N log N) average-case time complexity potentially degrading to O(N^2) for already sorted or reverse-sorted input, it elegantly demonstrates the power of tree structures for maintaining ordered data.

Summary

• Binary tree sorting uses a Binary Search Tree (BST) to sort elements.
• Process: Insert all elements into a BST, then perform an inorder traversal.
• BST Property: For any node, all left subtree values are smaller, and all right subtree values are larger.
• Inorder Traversal: Visits nodes in Left -> Root -> Right order, which yields elements in ascending order for a BST.
• Complexity: Average time complexity is O(N log N), but can degrade to O(N^2) in worst-case scenarios (e.g., highly unbalanced trees).
• Use Cases: More common for dynamic data management and ordered lookups than for static sorting of arrays.