DSA Tutorial

Binary Tree Structure

A binary tree can be represented by the following structure:

// Binary Tree Node Structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}
      

Types of Binary Trees

There are several variations of binary trees, including:

• Full Binary Tree: Every node has either 0 or 2 children.
• Perfect Binary Tree: All the internal nodes have two children, and all leaf nodes are at the same level.
• Complete Binary Tree: All levels are filled, except possibly for the last, which is filled from left to right.
• Degenerate (or pathological) Tree: Each parent node has only one child. This tree is essentially a linked list.

Binary Tree Traversal Methods

There are four main traversal methods in binary trees:

• Preorder Traversal: Visit the root node first, then recursively visit the left and right subtrees.
• Inorder Traversal: Traverse the left subtree first, then visit the root node, and finally traverse the right subtree.
• Postorder Traversal: Traverse the left and right subtrees first, and then visit the root node.
• Level Order Traversal: Visit all nodes level by level, from top to bottom and left to right.

Binary Tree Traversal Example

Here's a code example that demonstrates binary tree creation and various traversal methods:

// Preorder Traversal
void preorderTraversal(struct Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// Inorder Traversal
void inorderTraversal(struct Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

// Postorder Traversal
void postorderTraversal(struct Node* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->data);
}

// Level Order Traversal
void levelOrderTraversal(struct Node* root) {
    if (root == NULL) return;
    struct Queue* q = createQueue();
    enqueue(q, root);

    while (!isEmpty(q)) {
        struct Node* node = dequeue(q);
        printf("%d ", node->data);

        if (node->left) enqueue(q, node->left);
        if (node->right) enqueue(q, node->right);
    }
}
      

Applications of Binary Trees

Binary trees are widely used in various real-life applications:

• Expression Parsing: Binary trees are used to represent arithmetic expressions in compilers and evaluators.
• Huffman Encoding: Used in data compression algorithms like ZIP, GZIP, and MP3.
• Binary Search Trees (BST): Used in database indexing for efficient searching, insertion, and deletion.
• Decision Trees: Used in AI and machine learning for decision-making and classification tasks.
• File Systems: Binary trees are used in managing and organizing files in a computer’s file system.