Trees in C

So far, you have studied linear data structures such as arrays, stacks, queues, and linked lists.

Now we move to a non-linear data structure called a Tree.

Trees are used to represent hierarchical relationships.

What Is a Tree?

A tree is a collection of nodes arranged in a hierarchical structure.

Each tree has:

• A single root node
• Zero or more child nodes
• No cycles

Real-World Example

Think of a company organization chart:

• CEO at the top (root)
• Managers below
• Employees under managers

This structure forms a tree.

Basic Tree Terminology

• Root – Top node
• Parent – Node with children
• Child – Node connected below
• Leaf – Node with no children
• Edge – Connection between nodes

Binary Tree

A binary tree is a tree where each node has at most two children:

• Left child
• Right child

Binary trees are the foundation for many advanced structures.

Structure of a Tree Node

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

Creating a Tree 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;
}

Simple Binary Tree Example

Creating a tree manually:

struct Node* root = createNode(10);
root->left = createNode(5);
root->right = createNode(20);

Here:

• 10 is the root
• 5 is the left child
• 20 is the right child

Why Trees Are Important

• Efficient searching
• Fast insertion and deletion
• Hierarchical data representation

Where Trees Are Used

• File systems
• Databases
• Search engines
• Compilers

Mini Practice

• Create a binary tree with 3 nodes
• Assign left and right children
• Print root, left, and right values

Quick Quiz

Q1. What type of data structure is a tree?

Non-linear data structure

Q2. What is the top node called?

Root

Q3. How many children can a binary tree node have?

At most two

Q4. What is a leaf node?

A node with no children

Q5. Are trees used in real software systems?

Yes