Coming Soon

Tree Data Structure

A Tree is a non-linear hierarchical data structure used to store data in the form of connected nodes. Unlike arrays, stacks, queues, or linked lists that organize data linearly, a tree organizes data in parent-child relationships.

Trees are widely used in computer science because they provide efficient ways to store, search, insert, and manage hierarchical information.

Examples of hierarchical structures in real life include:

Family trees
Organization charts
Folder structures in operating systems
Website navigation systems
XML and HTML documents

Trees are one of the most important concepts in Data Structures and Algorithms (DSA).

Basic Terminologies of Tree

Understanding tree terminology is very important before learning tree operations.

Consider the following example:

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

1. Node

A node is the basic element of a tree that stores data.

In the above example:

A, B, C, D, E, F, and G

are nodes.

2. Root Node

The topmost node of a tree is called the root node.

Example: A is the root node.

A tree can have only one root node.

3. Parent Node

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

Example:

A is parent of B, C, and D
B is parent of E and F

4. Child Node

A node directly connected below another node is called a child node.

Example:

B, C, and D are children of A
E and F are children of B

5. Sibling Nodes

Nodes having the same parent are called siblings.

Example:

B, C, and D are siblings
E and F are siblings

6. Leaf Node

Nodes without children are called leaf nodes.

Example: C, E, F, and G are leaf nodes.

Leaf nodes are also known as terminal nodes.

7. Internal Node

A node with at least one child is called an internal node.

Example: A, B, and D

8. Edge

The connection between two nodes is called an edge.

Example:

A → B
B → E

A tree with n nodes always contains n - 1 edges.

9. Degree of a Node

The number of children of a node is called the degree of that node.

Example:

Degree of A = 3
Degree of B = 2
Degree of C = 0

10. Degree of Tree

The maximum degree among all nodes in a tree is called the degree of the tree.

Example:

The degree of the above tree is 3 because node A has 3 children.

11. Path

A sequence of connected nodes is called a path.

Example: A → B → F

12. Level of Node

The level represents the position of a node in the tree.

Example:

Node	Level
A	0
B, C, D	1
E, F, G	2

13. Height of Tree

The height of a tree is the length of the longest path from the root node to the deepest leaf node.

Example: Height = 2

14. Subtree

A smaller tree formed from a node and its descendants is called a subtree.

Example:

Subtree rooted at B:

      B
     / \
    E   F

Characteristics of Tree Data Structure

Hierarchical organization of data
Non-linear structure
Efficient searching and insertion
Dynamic memory allocation
Supports recursive operations

Types of Trees

There are different types of tree structures used for different purposes.

1. General Tree

A tree where a node can have any number of children.

Example:

        A
      / | | \
     B  C D  E

2. Binary Tree

A binary tree is a tree where each node can have at most two children.

These children are called:

Left child
Right child

Example:

3. Full Binary Tree

A binary tree where every node has either:

0 children, or
2 children

Example:

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

4. Complete Binary Tree

A binary tree in which all levels are completely filled except possibly the last level.

Nodes in the last level are filled from left to right.

Example:

5. Perfect Binary Tree

A binary tree where:

All internal nodes have two children
All leaf nodes are at the same level

Example:

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

6. Skewed Tree

A skewed tree is a tree where every node has only one child.

Types:

Left-skewed tree
Right-skewed tree

Example:

A
 \
  B
   \
    C

7. Binary Search Tree (BST)

A Binary Search Tree follows these rules:

Left subtree contains smaller values
Right subtree contains larger values

Example:

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

BST provides efficient searching.

Tree Traversal

Traversal means visiting all nodes of a tree in a specific order.

There are two major traversal categories:

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

Depth First Traversal (DFS)

DFS explores nodes deeply before moving to the next branch.

There are three types of DFS traversal.

1. Preorder Traversal

Traversal order:

Root → Left → Right

Example:

Preorder result:

A B D E C

2. Inorder Traversal

Traversal order:

Left → Root → Right

Inorder result:

D B E A C

3. Postorder Traversal

Traversal order:

Left → Right → Root

Postorder result:

D E B C A

Breadth First Traversal (Level Order Traversal)

Breadth First Traversal visits nodes level by level.

Example:

Traversal order:

A B C D E F

Queue data structure is commonly used for level-order traversal.

Operations on Tree

1. Insertion

Insertion means adding a new node into the tree.

In a binary tree, insertion is generally done level-wise.

In BST:

Smaller value goes to left subtree
Larger value goes to right subtree

Example:

Insert 60

2. Deletion

Deletion removes a node from the tree.

Deletion cases in BST:

Case 1: Deleting Leaf Node

Delete node with no children

Case 2: Deleting Node with One Child

The child replaces the deleted node.

Case 3: Deleting Node with Two Children

Replace the node with:

Inorder predecessor, or
Inorder successor

3. Searching

Searching means finding a particular node.

In BST:

Compare target value with current node
Move left or right accordingly

Searching in BST is efficient compared to linear structures.

Applications of Tree Data Structure

Trees are used in many real-world applications.

1. File Systems

Folders and files are organized hierarchically.

Example:

Root
 ├── Documents
 ├── Pictures
 └── Videos

2. Database Indexing

Databases use B-Trees and B+ Trees for fast searching.

3. Compiler Design

Syntax trees are used during parsing.

4. Artificial Intelligence

Decision trees are used in machine learning.

5. Computer Networks

Routing algorithms use tree structures.

6. HTML and XML Documents

Web pages are represented as tree structures.

7. Game Development

Game states and decision systems use trees.

Advantages of Tree Data Structure

1. Efficient Searching

Binary Search Trees provide fast searching.

2. Hierarchical Data Representation

Trees naturally represent parent-child relationships.

3. Dynamic Structure

Nodes can be inserted and deleted dynamically.

4. Better Organization

Large data can be organized systematically.

Disadvantages of Tree Data Structure

1. Complex Implementation

Trees are more difficult to implement compared to arrays.

2. Memory Overhead

Pointers require additional memory.

3. Balancing Issues

Unbalanced trees may reduce performance.

Time Complexity of Binary Search Tree Operations

Operation	Average Case	Worst Case
Searching	O(log n)	O(n)
Insertion	O(log n)	O(n)
Deletion	O(log n)	O(n)

Worst-case complexity occurs when the tree becomes skewed.

Space Complexity

For n nodes: O(n) because memory is required to store all nodes and pointers.

C Program for Binary Tree

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

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

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

void inorder(struct Node* root) {
    if(root == NULL)
        return;

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

int main() {
    struct Node* root = createNode(10);
    root->left = createNode(20);
    root->right = createNode(30);
    root->left->left = createNode(40);
    root->left->right = createNode(50);

    printf("Inorder Traversal: ");
    inorder(root);

    return 0;
}

Difference Between Linear Data Structure and Tree

Linear Data Structure	Tree Data Structure
Data arranged sequentially	Data arranged hierarchically
Single-level structure	Multi-level structure
Traversal is linear	Traversal is hierarchical
Examples: Array, Stack, Queue	Examples: BST, Heap, Trie

Conclusion

A Tree Data Structure is one of the most important non-linear data structures used in computer science. It organizes data hierarchically and supports efficient searching, insertion, deletion, and traversal operations. Different types of trees such as binary trees, binary search trees, heaps, and B-trees are widely used in operating systems, databases, artificial intelligence, networking, and web technologies.

Because of their flexibility and efficiency, trees play a major role in designing modern software systems and algorithms.

Introduction to Data Structure

Recursion

Stacks

Queue

Linked List

Trees

Sorting

Searching

Graph

Growth Functions

Tree Data Structure

Basic Terminologies of Tree

1. Node

2. Root Node

3. Parent Node

4. Child Node

5. Sibling Nodes

6. Leaf Node

7. Internal Node

8. Edge

9. Degree of a Node

10. Degree of Tree

11. Path

12. Level of Node

13. Height of Tree

14. Subtree

Characteristics of Tree Data Structure

Types of Trees

1. General Tree

2. Binary Tree

3. Full Binary Tree

4. Complete Binary Tree

5. Perfect Binary Tree

6. Skewed Tree

7. Binary Search Tree (BST)

Tree Traversal

Depth First Traversal (DFS)

1. Preorder Traversal

2. Inorder Traversal

3. Postorder Traversal

Breadth First Traversal (Level Order Traversal)

Operations on Tree

1. Insertion

2. Deletion

3. Searching

Applications of Tree Data Structure

1. File Systems

2. Database Indexing

3. Compiler Design

4. Artificial Intelligence

5. Computer Networks

6. HTML and XML Documents

7. Game Development

Advantages of Tree Data Structure

1. Efficient Searching

2. Hierarchical Data Representation

3. Dynamic Structure

4. Better Organization

Disadvantages of Tree Data Structure

1. Complex Implementation

2. Memory Overhead

3. Balancing Issues

Time Complexity of Binary Search Tree Operations

Space Complexity

C Program for Binary Tree

Difference Between Linear Data Structure and Tree

Conclusion