Trees | Data Structures

Introduction to Trees

Trees are a type of data structure that simulate a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. Trees are used to represent hierarchical relationships, such as organization structures, file systems, and more.

Basic Terminologies

Before we delve deeper into trees, it is important to understand some basic terminologies:

Node: Each element in a tree.
Root: The topmost node of a tree. There is only one root in a tree.
Edge: The link between two nodes.
Child: A node directly connected to another node when moving away from the root.
Parent: The converse notion of a child.
Leaf: A node with no children.
Subtree: A tree formed by a node and its descendants.
Height: The length of the longest path from the root to a leaf.

Binary Trees

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

Binary Tree Implementation in C

Below is a simple implementation of a binary tree in C:

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

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

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Binary Tree Created\n");
    return 0;
}

Tree Traversal

Tree traversal is a process of visiting all the nodes in a tree in a specific order. There are mainly three types of tree traversal:

Inorder Traversal (Left, Root, Right): Visit the left subtree, the root, and then the right subtree.
Preorder Traversal (Root, Left, Right): Visit the root, the left subtree, and then the right subtree.
Postorder Traversal (Left, Right, Root): Visit the left subtree, the right subtree, and then the root.

Inorder Traversal Implementation in C

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

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

// Inorder traversal
void inorderTraversal(struct Node* node) {
    if (node == NULL)
        return;

    inorderTraversal(node->left);
    printf("%d ", node->data);
    inorderTraversal(node->right);
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Inorder Traversal: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

Binary Search Trees (BST)

A binary search tree (BST) is a binary tree in which each node has a comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.

BST Operations

Common operations on a BST include:

Search: Find a node in the tree.
Insertion: Add a new node to the tree.
Deletion: Remove a node from the tree.

BST Insertion Implementation in C

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

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

// Insert a node
struct Node* insert(struct Node* node, int data) {
    if (node == NULL)
        return newNode(data);

    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);

    return node;
}

// Inorder traversal
void inorderTraversal(struct Node* node) {
    if (node == NULL)
        return;

    inorderTraversal(node->left);
    printf("%d ", node->data);
    inorderTraversal(node->right);
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder Traversal: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

Conclusion

Trees are a fundamental data structure used in computer science to represent hierarchical relationships. Understanding the basics of trees, including binary trees and binary search trees, is crucial for solving complex problems efficiently.

Trees in Data Structures