Data Structures and Algorithms in C (DSA)

📘 Chapter: Binary Trees & Representations: Hierarchical Data Structures

So far, we've primarily dealt with linear data structures like arrays and linked lists, where elements are arranged sequentially. Now, we're taking a significant leap into the world of non-linear data structures, starting with one of the most fundamental and versatile: the Binary Tree. Trees, in general, are hierarchical structures, resembling an upside-down tree with a root at the top and leaves at the bottom. Binary Trees are a special type of tree where each node has at most two children, typically referred to as the left child and the right child. Their structure allows for efficient searching, insertion, and deletion operations, forming the backbone for many advanced data structures and algorithms.

🌳 What is a Binary Tree? Core Concepts

A Binary Tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. Key terminology associated with trees:

• Root: The topmost node of the tree. A tree has only one root.
• Node: An element in the tree that holds data.
• Parent: A node that has one or more child nodes.
• Child: A node directly connected to another node when moving away from the root.
• Leaf (or External Node): A node that has no children.
• Internal Node: A node that has at least one child.
• Edge: The link between two nodes.
• Path: A sequence of nodes along the edges from one node to another.
• Depth of a Node: The number of edges from the root to that node. The root has a depth of 0.
• Height of a Node: The number of edges on the longest path from the node to a leaf. The height of a leaf node is 0.
• Height of a Tree: The height of its root node.
• Subtree: A tree formed by a node and all its descendants.

Types of Binary Trees:

• Full Binary Tree: Every node has either 0 or 2 children.
• Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.
• Perfect Binary Tree: All internal nodes have two children, and all leaf nodes are at the same depth (i.e., all levels are completely filled).
• Balanced Binary Tree: The heights of the left and right subtrees of every node differ by at most 1 (e.g., AVL Trees, Red-Black Trees). This prevents the tree from becoming skewed and degenerating into a linked list.
• Degenerate (or Skewed) Tree: Each parent node has only one child, resembling a linked list. This leads to O(n) performance for operations.

📊 Representing Binary Trees

Binary trees can be represented in several ways. The two most common methods are using arrays and using linked structures (pointers).

1. Array Representation (Implicit Representation)

This method is particularly suitable for complete binary trees or nearly complete binary trees, as it avoids wasting too much space. The nodes are stored in an array level by level from left to right.

• If a node is at index i (0-indexed):
• Its left child is at index 2 * i + 1
• Its right child is at index 2 * i + 2
• Its parent is at index (i - 1) / 2 (integer division)

// Array Representation Example (for a Complete Binary Tree) in C
#define MAX_NODES 100

int tree_array[MAX_NODES]; // Stores node values
// To represent an empty node, you might use a special value like -1 or INT_MIN/MAX

// Function to get left child index
int getLeftChild(int parent_idx) {
    int left_child_idx = 2 * parent_idx + 1;
    if (left_child_idx >= MAX_NODES || tree_array[left_child_idx] == -1) // Assuming -1 means empty
        return -1; // Or some indicator of invalid/empty
    return left_child_idx;
}

// Function to get right child index
int getRightChild(int parent_idx) {
    int right_child_idx = 2 * parent_idx + 2;
    if (right_child_idx >= MAX_NODES || tree_array[right_child_idx] == -1)
        return -1;
    return right_child_idx;
}

// Function to get parent index
int getParent(int child_idx) {
    if (child_idx == 0) return -1; // Root has no parent
    return (child_idx - 1) / 2;
}

// Example: Representing a simple tree
//          1
//         / \
//        2   3
//       / \
//      4   5
// tree_array: [1, 2, 3, 4, 5, -1, -1, ...] (assuming -1 for empty spots)
  

Advantages: Simple to implement, memory efficient for complete trees (no pointer overhead), good cache performance due to contiguous memory. Used extensively in implementing heaps.

Disadvantages: Wastes a lot of memory for sparse or skewed trees (many empty array slots). Insertion/deletion can be complex as it might require shifting many elements to maintain completeness, though this is less of an issue for fixed-size trees or heaps.

2. Linked Representation (Pointer-Based Representation)

This is the most common and flexible way to represent binary trees. Each node is an object (or struct in C) that contains:

• Data (value of the node)
• A pointer (or reference) to its left child
• A pointer (or reference) to its right child

// Linked Representation Example in C
#include <stdio.h>
#include <stdlib.h> // For malloc

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

// 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); // Exit if memory allocation fails
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Example: Building a simple tree
//          10
//         /  \
//        20   30
//       /
//      40
//
// int main() {
//     struct Node* root = createNode(10);
//     root->left = createNode(20);
//     root->right = createNode(30);
//     root->left->left = createNode(40);
//
//     // Tree is now built. You can traverse it, etc.
//     return 0;
// }
  

Advantages: Flexible for trees of any shape (full, skewed, sparse). Efficient for insertions and deletions as only pointers need to be updated. No wasted space for non-existent nodes.

Disadvantages: Requires more memory per node (due to pointers). Can have poorer cache performance due to scattered memory allocations. More complex to implement compared to array representation.

Binary Tree Example Visualization: Structure & Representation