Trees

Tree

Trees, in the context of computer science and data structures, are hierarchical data structures composed of nodes. Each node contains a value or data and references to its child nodes (if any). The topmost node in a tree is called the root, and the nodes at the bottom with no children are called leaves.

Here’s a rephrased version of the trees:

1. Root Node: The initial node in a tree structure is known as the root node.
2. Edge: An edge signifies a connection between two nodes within a tree.
3. Parent Node: A parent node refers to a node that possesses links to its child nodes. It is also called an internal node.
4. Child Nodes: A node may have zero, one, or multiple child nodes.
5. Single Parent Node: Each node in a tree can only have one parent node.
6. Leaf Nodes: Nodes lacking connections to other child nodes are termed as leaves or leaf nodes.
7. Tree Height: The height of a tree is the maximum count of edges from the root node to a leaf node. In the given tree, the height is 2.
8. Node Height: The height of a node refers to the greatest count of edges between the node and a leaf node.
9. Tree Size: The size of a tree denotes the total number of nodes it contains.

Basic Tree Structure

A tree follows a hierarchical structure, similar to a family tree.

        A  <-- Root
       / \
      B   C
     / \   \
    D   E   F  <-- Leaf nodes

• A is the root node.
• B and C are children of A.
• D, E, and F are leaf nodes.

Code Implementation in C

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

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

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

// Example usage
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("Root Node: %d\n", root->data);
    printf("Left Child of Root: %d\n", root->left->data);
    printf("Right Child of Root: %d\n", root->right->data);

    // Free allocated memory
    free(root->left->left);
    free(root->left->right);
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

Output:

Root Node: 1
Left Child of Root: 2
Right Child of Root: 3

Code Explanation

1. Defining the Node Structure

In a binary tree, each node has:

• data (to store the value)
• left (pointer to the left child)
• right (pointer to the right child)

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

Explanation:

• We define a structure Node with three members:
  • data → stores the integer value.
  • left → points to the left child node.
  • right → points to the right child node.

2. Function to Create a New Node

To avoid repetitive code, we define a function createNode() that:

1. Allocates memory for a new node using malloc().
2. Initializes the node with the given value.
3. Sets left and right pointers to NULL.

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

Explanation:

• malloc() dynamically allocates memory for a new node.
• We assign the value to data and set left and right pointers to NULL (as it’s a new node).

3. Creating the Tree

In the main() function, we create a simple binary tree.

int main() {
    struct Node* root = createNode(1);   // Root node
    root->left = createNode(2);          // Left child of root
    root->right = createNode(3);         // Right child of root
    root->left->left = createNode(4);    // Left child of node 2
    root->left->right = createNode(5);   // Right child of node 2

💡 Tree Representation:

        1
       / \
      2   3
     / \
    4   5

• Root (1) has two children (2 and 3).
• Node 2 has two children (4 and 5).
• Node 3 has no children.

4. Printing the Node Values

We display the data values of the root and its children.

    printf("Root Node: %d\n", root->data);
    printf("Left Child of Root: %d\n", root->left->data);
    printf("Right Child of Root: %d\n", root->right->data);

💡 Expected Output:

Root Node: 1
Left Child of Root: 2
Right Child of Root: 3

• This verifies that our tree structure is correctly formed.

5. Freeing Allocated Memory

Since we used malloc(), we must release the memory to prevent leaks.

free(root->left->left);
free(root->left->right);
free(root->left);
free(root->right);
free(root);

return 0;

💡 Explanation:

• We free() each node in bottom-up order to prevent memory leaks.

Summary

Trees are widely used in computer science due to their versatility and efficiency. They facilitate various operations such as searching, insertion, deletion, and traversal of data.

Here are some common types of trees:

1. Binary Tree: A binary tree is a tree in which each node has at most two children, referred to as the left child and the right child.
2. Binary Search Tree (BST): A binary search tree is a binary tree in which for each node, all nodes in its left subtree have values less than the node’s value, and all nodes in its right subtree have values greater than the node’s value. This property makes searching, insertion, and deletion operations efficient.
3. AVL Tree: An AVL tree is a self-balancing binary search tree in which the heights of the two child subtrees of any node differ by at most one. This balancing ensures that the tree remains balanced and maintains efficient operations..

Trees are used in various applications, including database indexing, file systems, network routing, and compilers.

Understanding trees and their associated algorithms is essential for effectively solving problems and designing efficient algorithms in computer science and programming.