A binary tree is a hierarchical data structure composed of nodes, each containing a data element and pointers to left and right child nodes. Its widely used in computer science for tasks like searching, sorting, and hierarchical representation.

Key Components of a Binary Tree

• Node: The fundamental unit, storing data and references to left and right children. Data can be of any type, typically integers or custom structures.
• Root Node: The topmost node with no parent, serving as the entry point for the tree.
• Child Node: Nodes directly connected to a parent, with zero, one, or two children. Left and right children represent subtrees.
• Leaf Node: Nodes without children, located at the tree's bottom.
• Parent Node: The node directly above a given node in the hierarchy.
• Depth: The level of a node, with the root at depth 0.
• Height: The maximum depth from the root to any leaf, indicating the tree's size.
• Types of Binary Trees: Include binary search trees (BST), balanced trees, full trees, and complete trees, based on node arrangement and properties.
• Traversal Methods: Techniques to visit all nodes in a specific order, such as preorder (root-left-right), inorder (left-root-right), postorder (left-right-root), and level-order traversal.

Implementation in C

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a binary tree node
typedef struct BinNode {
    int key;
    struct BinNode* leftChild;
    struct BinNode* rightChild;
} BinNode;

// Function to allocate memory for a new node
BinNode* makeNode(int val) {
    BinNode* newNode = (BinNode*)malloc(sizeof(BinNode));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation error\n");
        exit(EXIT_FAILURE);
    }
    newNode->key = val;
    newNode->leftChild = NULL;
    newNode->rightChild = NULL;
    return newNode;
}

// Insert a value into the binary search tree
BinNode* addNode(BinNode* root, int val) {
    if (root == NULL) {
        return makeNode(val);
    }
    if (val < root->key) {
        root->leftChild = addNode(root->leftChild, val);
    } else if (val > root->key) {
        root->rightChild = addNode(root->rightChild, val);
    }
    return root;
}

// Preorder traversal: root, left, right
void traversePreorder(BinNode* root) {
    if (root != NULL) {
        printf("%d ", root->key);
        traversePreorder(root->leftChild);
        traversePreorder(root->rightChild);
    }
}

// Inorder traversal: left, root, right
void traverseInorder(BinNode* root) {
    if (root != NULL) {
        traverseInorder(root->leftChild);
        printf("%d ", root->key);
        traverseInorder(root->rightChild);
    }
}

// Postorder traversal: left, right, root
void traversePostorder(BinNode* root) {
    if (root != NULL) {
        traversePostorder(root->leftChild);
        traversePostorder(root->rightChild);
        printf("%d ", root->key);
    }
}

// Deallocate memory for the entire tree
void freeTree(BinNode* root) {
    if (root != NULL) {
        freeTree(root->leftChild);
        freeTree(root->rightChild);
        free(root);
    }
}

int main() {
    BinNode* root = NULL;

    // Build a binary search tree with sample values
    root = addNode(root, 5);
    root = addNode(root, 3);
    root = addNode(root, 8);
    root = addNode(root, 1);
    root = addNode(root, 4);
    root = addNode(root, 7);
    root = addNode(root, 9);

    printf("Preorder traversal: ");
    traversePreorder(root);
    printf("\n");

    printf("Inorder traversal: ");
    traverseInorder(root);
    printf("\n");

    printf("Postorder traversal: ");
    traversePostorder(root);
    printf("\n");

    // Clean up memory
    freeTree(root);

    return 0;
}

Output Example

Preorder traversal: 5 3 1 4 8 7 9
Inorder traversal: 1 3 4 5 7 8 9
Postorder traversal: 1 4 3 7 9 8 5