Data Structures using C

Introduction to Tree

A Tree is a non-linear hierarchical data structure consisting of nodes connected by edges. A tree begins with a special node called the Root Node. Every node can have zero or more child nodes, forming a parent-child relationship.

Trees are particularly useful when information naturally follows a hierarchical structure. Examples include file directories, organization charts, family trees, and database indexing systems.

• Non-linear data structure
• Stores data hierarchically
• Consists of nodes and edges
• Contains one Root Node
• Supports efficient searching and sorting

Characteristics of Tree

• Hierarchical arrangement of data
• Contains one unique Root Node
• Every child node has exactly one parent
• May contain multiple levels
• Does not contain cycles
• Supports dynamic data organization
• Efficient for searching and traversal operations

Components of Tree

Root Node

The topmost node of the tree is called the Root Node. Every tree contains exactly one root node.

Parent Node

A node that has one or more child nodes is called a Parent Node.

Child Node

A node directly connected below another node is called a Child Node.

Leaf Node

A node that has no children is called a Leaf Node.

Internal Node

Any node having at least one child is called an Internal Node.

Edge

The connection between two nodes is called an Edge.

Level

The position of a node within the hierarchy of a tree is called its Level. The Root Node is at Level 0. Note: some textbooks start counting from Level 1 instead of Level 0. This module uses Level 0 as the root.

Height

The Height of a tree is the number of edges in the longest path from the root node to a leaf node.

Tree Representation

            A
          /   \
         B     C
        / \   / \
       D   E F   G

In the above tree, A is the Root Node. B and C are children of A. D, E, F, and G are Leaf Nodes because they do not have any children.

Degree, Depth, Height and Level

Understanding Degree, Depth, Height, and Level is important for analyzing tree structures and solving tree-related problems.

            A
          /   \
         B     C
        / \     \
       D   E     F

Degree of a Node

The Degree of a Node is the number of children it has.

• Degree(A) = 2
• Degree(B) = 2
• Degree(C) = 1
• Degree(D) = 0

Degree of a Tree

The Degree of a Tree is the maximum degree among all nodes.

• Degree(Tree) = 2

Level of a Node

The Level of a Node indicates its position in the hierarchy. The Root Node is considered Level 0.

• Level(A) = 0
• Level(B) = 1
• Level(C) = 1
• Level(D) = 2

Depth of a Node

Depth is the number of edges from the Root Node to a particular node. Depth and Level produce the same numerical value for every node. Both terms are commonly used in textbooks and refer to the same measurement.

• Depth(A) = 0
• Depth(B) = 1
• Depth(E) = 2

Height of the Tree

Height is the number of edges in the longest path from the Root Node to a Leaf Node.

• Height(Tree) = 2

Important Tree Terminology

• Root → Topmost node of the tree
• Parent → Node having one or more children
• Child → Node connected below a parent
• Sibling → Nodes sharing the same parent
• Leaf Node → Node with no children
• Internal Node → Node having at least one child
• Degree of Node → Number of children of a node
• Degree of Tree → Maximum degree among all nodes
• Path → Sequence of connected nodes
• Height → Longest path from root to leaf

Need for Tree

Trees are used whenever information must be represented in a hierarchical manner. They provide faster searching, insertion, and deletion compared to many linear data structures.

• File system organization
• Database indexing
• Expression evaluation
• Searching and sorting
• Hierarchical data representation
• Decision-making systems

Types of Trees

Trees are classified into different types based on their structure, properties, and applications. Each type is designed for specific requirements.

1. General Tree

In a General Tree, a node can have any number of child nodes.

          A
       /  |  \
      B   C   D
     / \
    E   F

Applications

• Organization charts
• Directory structures
• XML and HTML documents

2. Binary Tree

A Binary Tree is a tree in which each node can have at most two children known as the Left Child and Right Child.

          A
         / \
        B   C
       / \   \
      D   E   F

Characteristics

• Maximum two children per node
• Left Child and Right Child
• Most commonly used tree structure

3. Full Binary Tree

A Full Binary Tree is a binary tree in which every node has either zero children or exactly two children.

          A
         / \
        B   C
       / \ / \
      D  E F  G

4. Complete Binary Tree

A Complete Binary Tree is a binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.

          A
         / \
        B   C
       / \ /
      D  E F

5. Perfect Binary Tree

A Perfect Binary Tree is a binary tree in which all internal nodes have exactly two children and all leaf nodes are at the same level.

          A
         / \
        B   C
       / \ / \
      D  E F  G

6. Degenerate Tree

A Degenerate Tree is a tree in which every parent node has only one child. It behaves similarly to a linked list.

A
|
B
|
C
|
D

7. Binary Search Tree (BST)

A Binary Search Tree is a Binary Tree that follows a specific ordering rule:

• All values in left subtree are smaller
• All values in right subtree are larger
• Both subtrees are also BSTs

           50
         /    \
       30      70
      / \     / \
    20  40  60  80

8. AVL Tree

AVL Tree is a self-balancing Binary Search Tree where the height difference between left and right subtrees is at most one.

• Self-balancing
• Improves searching performance
• Maintains logarithmic height

9. B-Tree

A B-Tree is a self-balancing multiway search tree commonly used in databases and file systems.

         [20 40]
        /   |   \
      [10] [30] [50]

Applications

• Database indexing
• File systems
• Storage management

Tree Traversal Techniques

Traversal is the process of visiting every node in a tree exactly once in a specific order. Since trees are non-linear data structures, there is no single natural way to visit all nodes. Different traversal techniques are used depending on the application.

Tree traversals are broadly classified into:

• Depth First Traversal (DFS)
• Breadth First Traversal (BFS)

           A
         /   \
        B     C
       / \   / \
      D   E F   G

The above tree will be used throughout this section to understand various traversal techniques.

Depth First Traversal (DFS)

In Depth First Traversal, nodes are explored as deeply as possible before moving to another branch. DFS is commonly implemented using recursion or stacks.

The three major DFS traversals are:

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal

Preorder Traversal

In Preorder Traversal, the Root Node is visited first, followed by the Left Subtree and then the Right Subtree.

Preorder:

Root → Left → Right

Example

           A
         /   \
        B     C
       / \   / \
      D   E F   G

Traversal Sequence:

A → B → D → E → C → F → G

C Function

void preorder(struct Node* root){

    if(root==NULL)
        return;

    printf("%d ",root->data);

    preorder(root->left);
    preorder(root->right);
}

Time Complexity: O(n)

Inorder Traversal

In Inorder Traversal, the Left Subtree is visited first, followed by the Root Node and then the Right Subtree.

Inorder:

Left → Root → Right

Example

           A
         /   \
        B     C
       / \   / \
      D   E F   G

Traversal Sequence:

D → B → E → A → F → C → G

For Binary Search Trees, Inorder Traversal visits nodes in sorted order.

C Function

void inorder(struct Node* root){

    if(root==NULL)
        return;

    inorder(root->left);

    printf("%d ",root->data);

    inorder(root->right);
}

Time Complexity: O(n)

Postorder Traversal

In Postorder Traversal, the Left Subtree is visited first, followed by the Right Subtree and finally the Root Node.

Postorder:

Left → Right → Root

Example

           A
         /   \
        B     C
       / \   / \
      D   E F   G

Traversal Sequence:

D → E → B → F → G → C → A

C Function

void postorder(struct Node* root){

    if(root==NULL)
        return;

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

    printf("%d ",root->data);
}

Time Complexity: O(n)

Breadth First Traversal (Level Order Traversal)

Breadth First Traversal, also known as Level Order Traversal, visits nodes level by level from top to bottom. It is commonly implemented using a Queue.

Level Order:

Level 0 → A

Level 1 → B C

Level 2 → D E F G

Traversal Sequence:

A → B → C → D → E → F → G

C Function

Level Order Traversal is implemented using a Queue. A node is enqueued, and as each node is dequeued and visited, its left and right children are enqueued.

/* Requires #include<stdlib.h> */

void levelOrder(
    struct Node* root){

    if(root==NULL)
        return;

    struct Node* queue[100];
    int front=0, rear=0;

    queue[rear++]=root;

    while(front < rear){

        struct Node* curr=
        queue[front++];

        printf("%d ",
               curr->data);

        if(curr->left!=NULL)
            queue[rear++]=
            curr->left;

        if(curr->right!=NULL)
            queue[rear++]=
            curr->right;
    }
}

Applications

• Level-wise tree processing
• Shortest path algorithms
• Network routing
• Breadth First Search (BFS)

Traversal Comparison

Traversal Type      Order

Preorder            Root Left Right

Inorder             Left Root Right

Postorder           Left Right Root

Level Order         Level by Level

Traversal Flow Example

Consider the following Binary Tree:

          10
         /  \
       20    30
      / \   / \
    40  50 60  70

Preorder

10 → 20 → 40 → 50 → 30 → 60 → 70

Inorder

40 → 20 → 50 → 10 → 60 → 30 → 70

Postorder

40 → 50 → 20 → 60 → 70 → 30 → 10

Level Order

10 → 20 → 30 → 40 → 50 → 60 → 70

Complexity Analysis of Traversals

Traversal          Time Complexity

Preorder                 O(n)

Inorder                  O(n)

Postorder                O(n)

Level Order              O(n)

Every traversal visits each node exactly once. Therefore, all traversal techniques require O(n) time where n is the number of nodes present in the tree.

Tree Operations

Various operations can be performed on trees to insert, delete, search, and analyze nodes. These operations form the foundation of tree-based algorithms and are extensively used in Binary Trees and Binary Search Trees (BSTs).

In this section, examples are demonstrated using Binary Search Trees because insertion, searching, and deletion are clearly defined using ordering properties.

Search Operation

Searching determines whether a particular value exists within the tree.

In a Binary Search Tree, searching is efficient because values smaller than the current node are located in the left subtree, while larger values are located in the right subtree.

           50
         /    \
       30      70
      / \     / \
    20  40  60  80

To search for 60:

• Compare 60 with 50 → Move Right
• Compare 60 with 70 → Move Left
• 60 Found

Average Time Complexity: O(log n)

Worst Case: O(n)

Insert Operation

Insertion adds a new node while maintaining the Binary Search Tree property.

The new value is compared with existing nodes and inserted at the appropriate leaf position.

Initial Tree

         50
        /  \
      30    70
     / \   /
   20  40 60

Insert 80

• 80 > 50 → Move Right
• 80 > 70 → Move Right
• Right Child is NULL
• Insert 80

           50
         /    \
       30      70
      / \     / \
    20  40  60  80

Average Time Complexity: O(log n)

Delete Operation

Deletion is the most important and slightly complex tree operation. Three different cases may occur while deleting a node from a Binary Search Tree.

Case 1: Deleting a Leaf Node

If the node has no children, it can simply be removed.

Delete 20

       50
      /  \
    30    70
   /
 20

Since 20 is a leaf node, it can be deleted directly.

Case 2: Deleting a Node with One Child

The child replaces the deleted node.

Before Deletion

        50
       /  \
     30    70
    /
  20

Delete 30

        50
       /  \
     20    70

Case 3: Deleting a Node with Two Children

Replace the node with its Inorder Successor (smallest value in the right subtree). After copying the successor's value into the deleted node's position, the successor node must also be deleted from the right subtree to avoid duplicates.

           50
         /    \
       30      70
      / \     / \
    20  40  60  80

Delete 50

Inorder Successor = 60

Step 1: Copy 60 into root position
Step 2: Delete 60 from right subtree

           60
         /    \
       30      70
      / \       \
    20  40      80

Find Height of Tree

The Height of a tree is the number of edges in the longest path from the root node to a leaf node.

           A
         /   \
        B     C
       / \
      D   E

Longest Path:

A → B → D

Height = 2 Edges

Recursive Formula

Height =
1 + max(
height(left),
height(right)
)

Count Total Nodes

Counting nodes determines how many nodes are present in a tree.

           A
         /   \
        B     C
       / \   / \
      D   E F   G

Total Nodes = 7

Formula

Nodes =
1 +
Count(left) +
Count(right)

Count Leaf Nodes

A Leaf Node is a node having no children.

           A
         /   \
        B     C
       / \   / \
      D   E F   G

Leaf Nodes:

• D
• E
• F
• G

Number of Leaf Nodes = 4

Operation Flow Example

The following example demonstrates how insertion, searching, and deletion affect a Binary Search Tree.

Initial Tree

        50
       /  \
     30    70


Step 1: Insert(20)

        50
       /  \
     30    70
    /
   20


Step 2: Insert(40)

        50
       /  \
     30    70
    / \
   20 40


Step 3: Search(40)

Found


Step 4: Delete(20)

        50
       /  \
     30    70
       \
        40

This example demonstrates how Binary Search Trees maintain their ordering property after every operation.

Complexity Analysis of Tree Operations

Operation       Average      Worst

Search           O(log n)     O(n)

Insert           O(log n)     O(n)

Delete           O(log n)     O(n)

Find Height      O(n)         O(n)

Count Nodes      O(n)         O(n)

Count Leaves     O(n)         O(n)

Binary Search Trees provide logarithmic performance when the tree remains balanced. In the worst case, a highly skewed tree behaves like a linked list, resulting in O(n) complexity.

Tree Implementation in C

Trees are commonly implemented using linked structures where each node contains data and pointers to its child nodes. Unlike arrays, tree nodes are dynamically allocated in memory.

Binary Trees and Binary Search Trees are generally implemented using structures and pointers in C. All programs in this section require #include<stdlib.h> for dynamic memory functions such as malloc() and free().

Tree Node Structure

Each node contains:

• Data Field
• Pointer to Left Child
• Pointer to Right Child

struct Node{

    int data;

    struct Node* left;
    struct Node* right;
};

The left pointer stores the address of the left child, while the right pointer stores the address of the right child.

Creating a New Node

New nodes are dynamically created using malloc().

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

struct Node{

    int data;

    struct Node* left;
    struct Node* right;
};

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

The function allocates memory, stores the value, initializes child pointers to NULL, and returns the node address.

Creating a Binary Tree Manually

Nodes can be manually connected to create a Binary Tree.

struct Node* root=
createNode(10);

root->left=
createNode(20);

root->right=
createNode(30);

root->left->left=
createNode(40);

root->left->right=
createNode(50);

The resulting tree becomes:

          10
         /  \
       20    30
      / \
    40  50

Preorder Traversal Program

Visits Root → Left → Right.

void preorder(
    struct Node* root){

    if(root==NULL)
        return;

    printf("%d ",
           root->data);

    preorder(root->left);
    preorder(root->right);
}

Inorder Traversal Program

Visits Left → Root → Right.

void inorder(
    struct Node* root){

    if(root==NULL)
        return;

    inorder(root->left);

    printf("%d ",
           root->data);

    inorder(root->right);
}

Postorder Traversal Program

Visits Left → Right → Root.

void postorder(
    struct Node* root){

    if(root==NULL)
        return;

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

    printf("%d ",
           root->data);
}

Binary Search Tree Insertion

BST insertion places a node in its correct position according to the Binary Search Tree property.

struct Node* insert(
    struct Node* root,
    int value){

    if(root==NULL)
        return createNode(
               value);

    if(value <
       root->data)

       root->left=
       insert(
       root->left,
       value);

    else if(value >
            root->data)

       root->right=
       insert(
       root->right,
       value);

    return root;
}

Binary Search Tree Search

Searching compares the target value with the current node and moves left or right accordingly.

struct Node* search(
    struct Node* root,
    int key){

    if(root==NULL ||
       root->data==key)

       return root;

    if(key <
       root->data)

       return search(
              root->left,
              key);

    return search(
           root->right,
           key);
}

Finding Inorder Successor

During BST deletion, a node having two children is replaced by its Inorder Successor. The Inorder Successor is the smallest value present in the right subtree.

struct Node* minValueNode(
    struct Node* node){

    struct Node* current=
    node;

    while(current &&
          current->left!=NULL)

          current=
          current->left;

    return current;
}

Binary Search Tree Deletion

BST deletion handles three situations:

• Node has no children
• Node has one child
• Node has two children — replaced by Inorder Successor, then the successor is deleted from the right subtree

struct Node* deleteNode(
    struct Node* root,
    int key){

    if(root==NULL)
        return root;

    if(key < root->data)

        root->left=
        deleteNode(
        root->left,key);

    else if(key >
            root->data)

        root->right=
        deleteNode(
        root->right,key);

    else{

        if(root->left==
           NULL){

            struct Node* temp=
            root->right;

            free(root);

            return temp;
        }

        else if(root->right==
                NULL){

            struct Node* temp=
            root->left;

            free(root);

            return temp;
        }

        struct Node* temp=
        minValueNode(
        root->right);

        root->data=
        temp->data;

        root->right=
        deleteNode(
        root->right,
        temp->data);
    }

    return root;
}

Height of Tree Program

Height can be calculated recursively by finding the maximum height among left and right subtrees.

int max(int a,int b){

    return (a>b)?
            a:b;
}

int height(
    struct Node* root){

    if(root==NULL)
        return -1;

    return 1 +
           max(
           height(
           root->left),

           height(
           root->right));
}

The base case returns -1 for an empty subtree so that a tree containing only one node correctly returns height 0, which matches the definition of height as the number of edges in the longest root-to-leaf path. A single node has no edges below it, so its height is 0.

Count Total Nodes Program

The total number of nodes can be calculated recursively.

int countNodes(
    struct Node* root){

    if(root==NULL)
        return 0;

    return 1 +
           countNodes(
           root->left) +
           countNodes(
           root->right);
}

Count Leaf Nodes Program

A leaf node is a node having no children.

int countLeaves(
    struct Node* root){

    if(root==NULL)
        return 0;

    if(root->left==NULL &&
       root->right==NULL)

       return 1;

    return countLeaves(
           root->left) +
           countLeaves(
           root->right);
}

Complete BST Example

The following sequence creates a Binary Search Tree.

Insert:

50, 30, 70,
20, 40, 60, 80


Resulting BST

           50
         /    \
       30      70
      / \     / \
    20  40  60  80

Inorder Traversal Output:

20 30 40 50 60 70 80

The output appears in sorted order because inorder traversal of a Binary Search Tree always produces sorted data.

Comparison: Binary Tree vs Binary Search Tree

Feature              Binary Tree         BST

Ordering Rule         No                 Yes

Searching             O(n)               O(log n)*

Insertion             Any Position       Ordered

Sorted Output         No                 Yes

Inorder Traversal     Unsorted           Sorted

Implementation        Simple             More Structured

*For balanced Binary Search Trees, searching requires O(log n) time on average.

Applications of Trees

Trees are used extensively in computer science because they efficiently represent hierarchical and searchable data.

• Database indexing systems
• File and folder organization
• Operating systems
• Expression evaluation
• Compiler design
• Artificial Intelligence
• Decision support systems
• Network routing algorithms
• Auto-complete and dictionaries
• Search engines

Real Life Examples of Trees

• Family Tree Structure
• Company Organization Hierarchy
• Folder and File Systems
• University Administrative Structure
• Website Navigation Menus
• Tournament Brackets
• Decision Trees in Machine Learning
• Biological Classification Systems

Practical Example using Trees

One of the most common applications of trees is representing a computer file system.

Consider the following directory structure:

C:
|
|-- Documents
|    |-- Notes.txt
|    |-- Report.pdf
|
|-- Pictures
|    |-- Photo1.jpg
|    |-- Photo2.jpg
|
|-- Downloads
     |-- Setup.exe

The root directory acts as the Root Node, folders behave as Internal Nodes, and files act as Leaf Nodes.

Advantages of Trees

• Represents hierarchical relationships naturally
• Efficient searching and insertion
• Supports dynamic memory allocation
• Provides faster access than linear structures
• Useful for sorting and indexing
• Scalable for large datasets
• Foundation for advanced data structures

Limitations of Trees

• Implementation is more complex than arrays
• Requires additional memory for pointers
• Unbalanced trees can reduce performance
• Deletion operations can be complicated
• Recursive algorithms may consume stack memory

Summary

Trees are hierarchical non-linear data structures consisting of nodes connected by edges. They are widely used for representing structured data, supporting efficient searching, insertion, and deletion operations. Binary Search Trees improve search efficiency by maintaining an ordered arrangement of values. Tree traversal techniques such as Preorder, Inorder, Postorder, and Level Order enable systematic processing of nodes.

Interview Questions

1. What is a Tree?

A Tree is a hierarchical non-linear data structure consisting of nodes connected by edges.

2. What is the Root Node?

The topmost node of a tree is called the Root Node.

3. What is a Leaf Node?

A node with no children is called a Leaf Node.

4. What is the Height of a Tree?

Height is the number of edges in the longest path from the root node to a leaf node.

5. What is a Binary Tree?

A Binary Tree is a tree in which every node can have at most two children.

6. What is a Binary Search Tree?

A BST is a Binary Tree where left subtree values are smaller and right subtree values are larger than the parent node.

7. What is Inorder Traversal?

Inorder Traversal visits nodes in the order: Left → Root → Right.

8. Why does Inorder Traversal of BST produce sorted output?

Because all left subtree values are smaller and all right subtree values are larger than the current node.

9. What is Preorder Traversal?

Root → Left → Right.

10. What is Postorder Traversal?

Left → Right → Root.

11. What is Level Order Traversal?

Traversal performed level by level using a queue.

12. What is a Full Binary Tree?

Every node contains either 0 or 2 children.

13. What is a Complete Binary Tree?

All levels are completely filled except possibly the last, which is filled from left to right.

14. What is an AVL Tree?

An AVL Tree is a self-balancing Binary Search Tree.

15. What is a B-Tree?

A self-balancing multiway search tree commonly used in databases and file systems.

16. What is the average search complexity of a BST?

O(log n)

17. What is the worst-case search complexity of a BST?

O(n)

18. Why are Trees preferred over Linked Lists for searching?

Trees can provide logarithmic search performance whereas linked lists generally require linear searching.

19. Which traversal is used to delete a tree?

Postorder Traversal because child nodes are processed before their parent nodes.

20. Give two applications of Trees.

Database indexing and file system organization.

21. What is the difference between a Full Binary Tree and a Complete Binary Tree?

In a Full Binary Tree, every node has either 0 or 2 children. In a Complete Binary Tree, all levels are completely filled except possibly the last level, which is filled from left to right.