DSA Tutorial

Types of Trees

Some of the most commonly used tree types in DSA include:

• Binary Tree: A tree where each node has at most two children.
• Binary Search Tree (BST): A binary tree where the left child is smaller than the parent node, and the right child is larger.
• AVL Tree: A self-balancing binary search tree where the difference in heights between left and right subtrees is at most 1.
• Heap Tree: A binary tree that satisfies the heap property, where the key of the parent is either greater or smaller than the keys of its children.
• Trie: A tree used for storing a dynamic set of strings, where nodes represent characters.

Tree Components

A tree consists of the following components:

• Root: The topmost node of the tree, where the tree starts.
• Node: An element that contains data and references to its child nodes.
• Edge: The connection between two nodes.
• Leaf: A node that does not have any children.
• Parent and Child: A node that is directly connected to another node is the parent, and the connected node is its child.
• Subtree: A tree formed by a node and its descendants.

Tree Traversal

Tree traversal refers to visiting all nodes in a specific order. The common types of tree traversal are:

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

Binary Tree Example

Below is a simple example of a binary tree 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;
}

// 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);
}

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

    printf("Preorder Traversal: ");
    preorderTraversal(root);
    printf("\n");

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

    printf("Postorder Traversal: ");
    postorderTraversal(root);
    printf("\n");

    return 0;
}
      

Applications of Trees

Trees are widely used in various computer science applications:

• Database Indexing: Trees, especially B-trees and AVL trees, are used to index databases for fast searching.
• File System Representation: File systems like NTFS and ext4 are implemented using tree structures, where each node represents a file or directory.
• XML/HTML Parsers: Trees are used to represent hierarchical document structures like XML or HTML documents.
• Decision Trees: Decision trees are used in machine learning and AI for classification and regression tasks.
• Expression Evaluation: Trees are used in parsing mathematical expressions and evaluating them in compilers.