TECHNOCRATS INSTITUTE OF TECHNOLOGY,BHOPAL

Department of computer science and engineering

SUBJECT : - Data Structure & Algorithms
By: Er.Chandan kumar

➢ What is Data Structure ?

• Data structures are the fundamental building blocks of computer programming. They
define how data is organized, stored, and manipulated within a program.
Understanding data structures is very important for developing efficient and effective
algorithms.
• A data structure is not only used for organizing the data. It is also used for processing,
retrieving, and storing data. There are different basic and advanced types of data
structures that are used in almost every program or software system that has been
developed.
➢ Classification of Data Structure:

According to the data types, the data structure is divided into two categories,
namely:
▪ Primitive Data Structures
▪ Non-Primitive Data Structures
➢ Primitive Data Structures:
This type of data structure stores the value of a particular data type. For example, an
integer data structure can store the value of only an integer. A primitive data
structure cannot be NULL.
 ❖ The following are the primitive data structures:
▪ Integer: It represents a whole number data type with no decimal places.
For example, int num = 30
▪ Float: It is a data type with decimal precision.
For example, float num = 2346.9875
▪ Character: It represents a single character.
For example, char name = “M”
▪ Boolean: It returns true or false values for a condition specified.
For example, boolean value = “true”
➢ Non-Primitive Data Structures:
These data structures are capable of storing values of more than one data type. The
size of the non-primitive data structure depends on the type of data it will store. For
example, a list (a non-primitive data structure) can store the values of various data
types. It can contain a NULL value.
➢ The following are some of the non-primitive data structures:
▪ List: A list is a linear type of data structure. This data structure holds an ordered list of
elements.
For example,
list_of_networks [“Airtel”, ”Jio”, “Idea”]
▪ Arrays: An array is also a linear data structure that stores a collection of data having
the same data type. It has a fixed size, which means it stores data in a contagious
memory location of the same data type (int, float, boolean, text, and others).
For example,
int[] numbers = {1, 2, 3, 4, 5}
▪ Queue: A Queue is a data structure that arranges items in a specific order and
follows the First-In-First-Out (FIFO) method for accessing elements. It is commonly
employed in building priority queuing systems and handling threads in multithreading
scenarios.
For example,
String[] names = {"Alice", "Charlie", "David", "Emily"};
▪ Stack: Based on the principle ‘last in, first out’ or LIFO, a stack is an abstract data type
that is composed of homogenous pieces. It is used for push and pop operations that
are applied on top of the stack. While the pop operation is responsible for removing
an element from the top spot, the push operation adds an element to the stack.
For example,
stack = [1,2,3,4,5]
 ▪ Tree: This is a non-linear and hierarchical data structure. A tree is a hierarchical
structure with nodes connected by edges, with the root being the top node and child
nodes below it.
For example,
tree = Tree(1, Tree(2, 2.1, 2.2), Tree(3, 3.1))

➢ Linear Data Structure: Data structure in which data elements are arranged
sequentially or linearly, where each element is attached to its previous and next
adjacent elements, is called a linear data structure.
Example: Array, Stack, Queue, Linked List, etc.
➢ Static Data Structure: Static data structure has a fixed memory size. It is easier to
access the elements in a static data structure.
Example: array.
➢ Dynamic Data Structure: In dynamic data structure, the size is not fixed. It can be
randomly updated during the runtime which may be considered efficient concerning
the memory (space) complexity of the code.
Example: Queue, Stack, etc.
➢ Non-Linear Data Structure: Data structures where data elements are not placed
sequentially or linearly are called non-linear data structures. In a non-linear data
structure, we can’t traverse all the elements in a single run only.
Examples: Trees and Graphs.
➢ Need Of Data structure :
1. Data structure modification is easy.
2. It requires less time.
3. Save storage memory space.
4. Data representation is easy.
5. Easy access to the large database.
➢ Advantages & Disadvantages of Data Structure:
➢ Advantages of Data Structure:
Data structures offer a wide range of benefits for creating and maintaining code in
programming languages. Some of these advantages are:

1) Efficient Storage
Data structures provide efficient storage by organizing the data effectively, which facilitates
quick retrieval and maintenance of the data in the system. The memory allocation takes
place according to the data types used in the data structure.

2) Easy Data Processing

Various data structures are used for specific purposes like organizing, processing, retrieving,
and storing data. These structures enable users to access and work with data efficiently.
Data structures simplify data processing and enable faster sorting and searching for specific
data within a large data set. The data structures convert raw data into a machine-readable
format and develop algorithms for data processing.

3) Develop Algorithms
Algorithms for data structures help organize and access information in a structured manner.
These algorithms take into account the format of the data as well as any actions that can be
performed on it. Their goal is to find the most efficient way to store and manipulate data
within the structure while also allowing for easy navigation. By utilizing these algorithms,
complex issues can be resolved with efficiency.

4) Reusability of Data
One of the fundamental advantages of data structure is that it offers data reusability. It
enables the creation of data in specific formats, which can then be stored in libraries,
allowing different clients to utilize and access the data as needed. Therefore, data can be
reused in multiple ways and purposes. This makes it easier to create efficient and dynamic
algorithms that can be used for different applications.

5) Provide Built-in Functions

Different programming languages offer diverse data structures equipped with a variety of
built-in functions. These functions make the most efficient use of specific databases and
enhance data manipulation capabilities. For example, data structures provide built-in
functions, such as search, sort, filter, and merge, which enable us to manipulate data more
effectively.
6) Supports Data Abstraction
The abstract data type in data structures helps support data abstraction. Data abstraction is
the process of hiding internal functions and displaying relevant and basic information. An
abstract data type supports the use of complex data structures with complex functions.
They can customize any data structure according to how it will be used and enable reusing
code by calling its functions without writing repetitive code. Examples of abstract data
structures include lists, queues, stacks, etc.

7) Saves Programmer’s Time

Data structures streamline the process of organizing and accessing data, which helps save
time. Developers can access data quickly and efficiently without having to manually search
through large amounts of data by selecting the appropriate data structure for their
program.

➢ Disadvantages of Data Structure:

1) Difficult to Handle for Beginners:
Working on simple and complex data structures requires good programming skills and
experience. A new developer may find it difficult to handle complex data structures.
2) Slower Data Structure Access:
Although different data types are available to allocate memory within the system, some of
the more complex data structures’ memory access might become slow and sluggish at
times.
3) Initial Quality Testing Takes Time:
Building algorithms is a necessary step in the process of designing a data structure from
scratch. Initially, it takes a lot of quality testing time, especially if the complexity of the data
structure is high.
4) High Maintenance:
Handling large data sets, especially big data, requires the use of complex data structures
and algorithms along with physical infrastructure. This will require a high cost of
maintenance for the smooth functioning of the programs.
5) Requires Comprehensive Planning:
Implementing and managing data structures without prior preparation and planning is
challenging. You need sophisticated calculations and tremendous efforts to outline the use
of data structures in your program.
➢ WHAT IS DATA TYPE:
A data type is a characteristic of data that defines how a computer system interprets its
value. Data types are used to ensure that data is collected in the correct format and that the
value of each property is as expected.

➢ Some common data types include:

C++ supports the following data types:
1. Primary or Built-in or Fundamental data type
2. Derived data types
3. User-defined data types
 ➢ Data Types in C++ are Mainly Divided into 3 Types:
1. Primitive Data Types: These data types are built-in or predefined data types and can be
used directly by the user to declare variables. example: int, char, float, bool, etc. Primitive
data types available in C++ are:
• Integer
• Character
• Boolean
• Floating Point
• Double Floating Point
• Valueless or Void
• Wide Character
2. Derived Data Types: Derived data types that are derived from the primitive or built-in
datatypes are referred to as Derived Data Types. These can be of four types namely:
• Function
• Array
• Pointer
• Reference
3. Abstract or User-Defined Data Types: Abstract or User-Defined data types are defined
by the user itself. Like, defining a class in C++ or a structure. C++ provides the following
user-defined datatypes:
• Class
• Structure
• Union
• Enumeration
• Typedef defined Datatype
➢ Primitive Data Types:
• Integer: The keyword used for integer data types is int. Integers typically require 4
bytes of memory space and range from -2147483648 to 2147483647.
• Character: Character data type is used for storing characters. The keyword used for
the character data type is char. Characters typically require 1 byte of memory space
and range from -128 to 127 or 0 to 255.
• Boolean: Boolean data type is used for storing Boolean or logical values. A Boolean
variable can store either true or false. The keyword used for the Boolean data type
is bool.
• Floating Point: Floating Point data type is used for storing single-precision floating-
point values or decimal values. The keyword used for the floating-point data type
is float. Float variables typically require 4 bytes of memory space.
• Double Floating Point: Double Floating Point data type is used for storing double-
precision floating-point values or decimal values. The keyword used for the double
floating-point data type is double. Double variables typically require 8 bytes of
memory space.
• void: Void means without any value. void data type represents a valueless entity. A
void data type is used for those function which does not return a value.
• Wide Character: Wide character data type is also a character data type but this data
type has a size greater than the normal 8-bit data type. Represented by wchar_t. It is
generally 2 or 4 bytes long.
• sizeof() operator: sizeof() operator is used to find the number of bytes occupied by a
variable/data type in computer memory.
Datatype Modifiers
As the name suggests, datatype modifiers are used with built-in data types to modify the
length of data that a particular data type can hold.

➢ Data type modifiers available in C++ are:

• Signed
• Unsigned
• Short
• Long
The below table summarizes the modified size and range of built-in datatypes when
combined with the type modifiers:
Data Type Size (in bytes) Range

short int 2 -32,768 to 32,767

unsigned short int 2 0 to 65,535

unsigned int 4 0 to 4,294,967,295

int 4 -2,147,483,648 to 2,147,483,647

long int 4 -2,147,483,648 to 2,147,483,647

unsigned long int 4 0 to 4,294,967,295

 Data Type Size (in bytes) Range

long long int 8 -(2^63) to (2^63)-1

unsigned long long int 8 0 to 18,446,744,073,709,551,615

signed char 1 -128 to 127

unsigned char 1 0 to 255

float 4 -3.4×10^38 to 3.4×10^38

double 8 -1.7×10^308 to1.7×10^308

long double 12 -1.1×10^4932 to1.1×10^4932

wchar_t 2 or 4 1 wide character

Name Expresses

CHAR_MIN The minimum value for an object of type char

CHAR_MAX Maximum value for an object of type char

SCHAR_MIN The minimum value for an object of type Signed char

SCHAR_MAX Maximum value for an object of type Signed char

UCHAR_MAX Maximum value for an object of type Unsigned char

CHAR_BIT Number of bits in a char object

 Name Expresses

MB_LEN_MAX Maximum number of bytes in a multi-byte character

SHRT_MIN The minimum value for an object of type short int

SHRT_MAX Maximum value for an object of type short int

USHRT_MAX Maximum value for an object of type Unsigned short int

INT_MIN The minimum value for an object of type int

INT_MAX Maximum value for an object of type int

UINT_MAX Maximum value for an object of type Unsigned int

LONG_MIN The minimum value for an object of type long int

LONG_MAX Maximum value for an object of type long int

ULONG_MAX Maximum value for an object of type Unsigned long int

LLONG_MIN The minimum value for an object of type long long int

LLONG_MAX Maximum value for an object of type long long int

ULLONG_MAX Maximum value for an object of type Unsigned long long int

➢ Differences between data type and data structure:

Data Type Data Structure

The data type is the form of a variable to Data structure is a collection of different
which a value can be assigned. It defines kinds of data. That entire data can be
 Data Type Data Structure

that the particular variable will assign the represented using an object and can be
values of the given data type only. used throughout the program.

It can hold value but not data. Therefore, It can hold multiple types of data within a
it is dataless. single object.

The implementation of a data type is Data structure implementation is known

known as abstract implementation. as concrete implementation.

There is no time complexity in the case of In data structure objects, time complexity
data types. plays an important role.

While in the case of data structures, the

In the case of data types, the value of data data and its value acquire the space in the
is not stored because it only represents computer’s main memory. Also, a data
the type of data that can be stored. structure can hold different kinds and
types of data within one single object.

Data type examples are int, float, double, Data structure examples are stack, queue,
etc. tree, etc.

• Linear data structure: Data structure in which data elements are arranged
sequentially or linearly, where each element is attached to its previous and next
adjacent elements, is called a linear data structure.
Examples of linear data structures are array, stack, queue, linked list, etc.
o Static data structure: Static data structure has a fixed memory size. It is
easier to access the elements in a static data structure.
An example of this data structure is an array.
o Dynamic data structure: In the dynamic data structure, the size is not fixed.
It can be randomly updated during the runtime which may be considered
efficient concerning the memory (space) complexity of the code.
Examples of this data structure are queue, stack, etc.
• Non-linear data structure: Data structures where data elements are not placed
sequentially or linearly are called non-linear data structures. In a non-linear data
structure, we can’t traverse all the elements in a single run only.
Examples of non-linear data structures are trees and graphs .
 Arrays:
• An array is a linear data structure and it is a collection of items stored at contiguous
memory locations. The idea is to store multiple items of the same type together in
one place. It allows the processing of a large amount of data in a relatively short
period. The first element of the array is indexed by a subscript of 0. There are
different operations possible in an array, like Searching, Sorting, Inserting,
Traversing, Reversing, and Deleting.

➢ Characteristics of an Array:
An array has various characteristics which are as follows:
• Homogeneous Elements: All elements within an array must be of the same data type.
• Contiguous Memory Allocation: In most programming languages, elements in an
array are stored in contiguous (adjacent) memory locations.
• Zero-Based Indexing: In many programming languages, arrays use zero-based
indexing, which means that the first element is accessed with an index of 0, the
second with an index of 1, and so on.
• Random Access: Arrays provide constant-time (O(1)) access to elements. This means
that regardless of the size of the array, it takes the same amount of time to access
any element based on its index.
• Arrays use an index-based data structure which helps to identify each of the elements
in an array easily using the index.
• If a user wants to store multiple values of the same data type, then the array can be
utilized efficiently.
• An array can also handle complex data structures by storing data in a two-dimensional
array.
• An array is also used to implement other data structures like Stacks, Queues, Heaps,
Hash tables, etc.
• The search process in an array can be done very easily.

➢ Operations performed on array:

• Initialization: An array can be initialized with values at the time of declaration or later
using an assignment statement.

• Accessing elements: Elements in an array can be accessed by their index, which starts
from 0 and goes up to the size of the array minus one.
• Searching for elements: Arrays can be searched for a specific element using linear
search or binary search algorithms.
• Sorting elements: Elements in an array can be sorted in ascending or descending
order using algorithms like bubble sort, insertion sort, or quick sort.
• Inserting elements: Elements can be inserted into an array at a specific location, but
this operation can be time-consuming because it requires shifting existing elements in
the array.
• Deleting elements: Elements can be deleted from an array by shifting the elements
that come after it to fill the gap.
• Updating elements: Elements in an array can be updated or modified by assigning a
new value to a specific index.
• Traversing elements: The elements in an array can be traversed in order, visiting each
element once.
➢ Applications of Array:
Different applications of an array are as follows:
• An array is used in solving matrix problems.
• Database records are also implemented by an array.
• It helps in implementing a sorting algorithm.
• It is also used to implement other data structures like Stacks, Queues, Heaps, Hash
tables, etc.
• An array can be used for CPU scheduling.
• Can be applied as a lookup table in computers.
• Arrays can be used in speech processing where every speech signal is an array.
• The screen of the computer is also displayed by an array. Here we use a
multidimensional array.
• The array is used in many management systems like a library, students, parliament,
etc.
• The array is used in the online ticket booking system. Contacts on a cell phone are
displayed by this array.
• In games like online chess, where the player can store his past moves as well as
current moves. It indicates a hint of position.
• To save images in a specific dimension in the android Like 360*1200
➢ Real-Life Applications of Array:
• An array is frequently used to store data for mathematical computations.
• It is used in image processing.
• It is also used in record management.
• Book pages are also real-life examples of an array.
• It is used in ordering boxes as well.
 ➢ Types of arrays:
• One-Dimensional Array: This is the simplest form of an array, which consists of a
single row of elements, all of the same data type. Elements in a 1D array are accessed
using a single index.

• Two-Dimensional Array: A two-dimensional array, often referred to as a matrix or 2D

array, is an array of arrays. It consists of rows and columns, forming a grid-like
structure. Elements in a 2D array are accessed using two indices, one for the row and
one for the column.

• Multi-Dimensional Array: Arrays can have more than two dimensions, leading to
multi-dimensional arrays. These are used when data needs to be organized in a multi-
dimensional grid.

2. Linked List
A Linked List is a linear data structure which looks like a chain of nodes, where each node
contains a data field and a reference(link) to the next node in the list. Unlike Arrays,
Linked List elements are not stored at a contiguous location.
Common Features of Linked List:
• Node: Each element in a linked list is represented by a node, which contains two
components:
o Data: The actual data or value associated with the element.
o Next Pointer(or Link): A reference or pointer to the next node in the linked
list.
• Head: The first node in a linked list is called the “head.” It serves as the starting point
for traversing the list.
• Tail: The last node in a linked list is called the “tail.”
Types of Linked Lists:
• Singly-linked list
• Doubly linked list
• Circular linked list
• Doubly circular linked list

➢ Singly Linked List:

• In this type of linked list, every node stores the address or reference of the next node
in the list and the last node has the next address or reference as NULL. For example:
1->2->3->4->NULL

➢ Doubly Linked Lists:

• In a doubly linked list, each node has two pointers: one pointing to the next node and
one pointing to the previous node. This bidirectional structure allows for efficient
traversal in both directions.

➢ Circular Linked Lists:

• A circular linked list is a type of linked list in which the first and the last nodes are
also connected to each other to form a circle, there is no NULL at the end.
Types of Linked List operations:
• Accessing Elements: Accessing a specific element in a linked list takes O(n) time since
nodes are stored in non conitgous locations so random access if not possible.
• Searching: Searching of a node in linked list takes O(n) time as whole list needs to
travesed in worst case.
• Insertion: Insertion takes O(1) time if we are at the position where we have to insert
an element.
• Deletion: Deletion takes O(1) time if we know the position of the element to be
deleted.
➢ Characteristics of a Linked list:
A linked list has various characteristics which are as follows:
• A linked list uses extra memory to store links.
• During the initialization of the linked list, there is no need to know the size of the
elements.
• Linked lists are used to implement stacks, queues, graphs, etc.
• The first node of the linked list is called the Head.
• The next pointer of the last node always points to NULL.
• In a linked list, insertion and deletion are possible easily.
• Each node of the linked list consists of a pointer/link which is the address of the next
node.
• Linked lists can shrink or grow at any point in time easily.
➢ Applications of the Linked list:
Different applications of linked lists are as follows:
• Linked lists are used to implement stacks, queues, graphs, etc.
• Linked lists are used to perform arithmetic operations on long integers.
• It is used for the representation of sparse matrices.
• It is used in the linked allocation of files.
• It helps in memory management.
• It is used in the representation of Polynomial Manipulation where each polynomial
term represents a node in the linked list.
• Linked lists are used to display image containers. Users can visit past, current, and
next images.
• They are used to store the history of the visited page.
• They are used to perform undo operations.
• Linked are used in software development where they indicate the correct syntax of a
tag.
• Linked lists are used to display social media feeds.

3. Stack Data Structure:

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle,
meaning that the last element added to the stack is the first one to be removed.
 ➢ Types of Stacks:
• Fixed Size Stack: As the name suggests, a fixed size stack has a fixed size and cannot
grow or shrink dynamically. If the stack is full and an attempt is made to add an
element to it, an overflow error occurs. If the stack is empty and an attempt is made
to remove an element from it, an underflow error occurs.
• Dynamic Size Stack: A dynamic size stack can grow or shrink dynamically. When the
stack is full, it automatically increases its size to accommodate the new element, and
when the stack is empty, it decreases its size. This type of stack is implemented using
a linked list, as it allows for easy resizing of the stack.
➢ Stack Operations:
• push(): When this operation is performed, an element is inserted into the stack.
• pop(): When this operation is performed, an element is removed from the top of the
stack and is returned.
• top(): This operation will return the last inserted element that is at the top without
removing it.
• size(): This operation will return the size of the stack i.e. the total number of elements
present in the stack.
• isEmpty(): This operation indicates whether the stack is empty or not.
Characteristics of a Stack:
Stack has various different characteristics which are as follows:
• Stack is used in many different algorithms like Tower of Hanoi, tree traversal,
recursion, etc.
• Stack is implemented through an array or linked list.
• It follows the Last In First Out operation i.e., an element that is inserted first will pop
in last and vice versa.
• The insertion and deletion are performed at one end i.e. from the top of the stack.
• In stack, if the allocated space for the stack is full, and still anyone attempts to add
more elements, it will lead to stack overflow.
Applications of Stack:
Different applications of Stack are as follows:
• The stack data structure is used in the evaluation and conversion of arithmetic
expressions.
• It is used for parenthesis checking.
• While reversing a string, the stack is used as well.
• Stack is used in memory management.
• It is also used for processing function calls.
• The stack is used to convert expressions from infix to postfix.
• The stack is used to perform undo as well as redo operations in word processors.
• The stack is used in virtual machines like JVM.
• The stack is used in the media players. Useful to play the next and previous song.
• The stack is used in recursion operations.

4. Queue Data Structure:

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. In a
queue, the first element added is the first one to be removed.

➢ Types of Queue:

• Input Restricted Queue: This is a simple queue. In this type of queue, the input can
be taken from only one end but deletion can be done from any of the ends.

• Output Restricted Queue: This is also a simple queue. In this type of queue, the input
can be taken from both ends but deletion can be done from only one end.
• Circular Queue: This is a special type of queue where the last position is connected
back to the first position. Here also the operations are performed in FIFO order. To
know more refer this.
• Double-Ended Queue (Dequeue): In a double-ended queue the insertion and
deletion operations, both can be performed from both ends. To know more refer this.
• Priority Queue: A priority queue is a special queue where the elements are accessed
based on the priority assigned to them. To know more refer this.
➢ Operation performed on queue:
• Enqueue(): Adds (or stores) an element to the end of the queue..
• Dequeue(): Removal of elements from the queue.
• Peek() or front(): Acquires the data element available at the front node of the queue
without deleting it.
• rear(): This operation returns the element at the rear end without removing it.
• isFull(): Validates if the queue is full.
• isNull(): Checks if the queue is empty.
 ➢ Characteristics of a Queue:

The queue has various different characteristics which are as follows:

• The queue is a FIFO (First In First Out) structure.

• To remove the last element of the Queue, all the elements inserted before the new
element in the queue must be removed.
• A queue is an ordered list of elements of similar data types.
➢ Applications of Queue:
Different applications of Queue are as follows:
• Queue is used for handling website traffic.
• It helps to maintain the playlist in media players.
• Queue is used in operating systems for handling interrupts.
• It helps in serving requests on a single shared resource, like a printer, CPU task
scheduling, etc.
• It is used in the asynchronous transfer of data e.g. pipes, file IO, and sockets.
• Queues are used for job scheduling in the operating system.
• In social media to upload multiple photos or videos queue is used.
• To send an e-mail queue data structure is used.
• To handle website traffic at a time queues are used.
• In Windows operating system, to switch multiple applications.

➢ Advantages of Linear Data Structures:

• Efficient data access: Elements can be easily accessed by their position in the
sequence.
• Dynamic sizing: Linear data structures can dynamically adjust their size as elements
are added or removed.
• Ease of implementation: Linear data structures can be easily implemented using
arrays or linked lists.
• Versatility: Linear data structures can be used in various applications, such as
searching, sorting, and manipulation of data.
• Simple algorithms: Many algorithms used in linear data structures are simple and
straightforward.
➢ Disadvantages of Linear Data Structures:
• Limited data access: Accessing elements not stored at the end or the beginning of the
sequence can be time-consuming.
• Memory overhead: Maintaining the links between elements in linked lists and
pointers in stacks and queues can consume additional memory.
• Complex algorithms: Some algorithms used in linear data structures, such as
searching and sorting, can be complex and time-consuming.
• Inefficient use of memory: Linear data structures can result in inefficient use of
memory if there are gaps in the memory allocation.
• Unsuitable for certain operations: Linear data structures may not be suitable for
operations that require constant random access to elements, such as searching for an
element in a large dataset.
Tree:

• A tree is a non-linear and hierarchical data structure where the elements are
arranged in a tree-like structure. In a tree, the topmost node is called the root
node. Each node contains some data, and data can be of any type. It consists of a
central node, structural nodes, and sub-nodes which are connected via edges.
Different tree data structures allow quicker and easier access to the data as it is a
non-linear data structure. A tree has various terminologies like Node, Root, Edge,
Height of a tree, Degree of a tree, etc.
➢ There are different types of Tree-like
1) Binary Tree,
2) Binary Search Tree,
3) AVL Tree,
4) B-Tree, etc.
 ➢ Characteristics of a Tree:
The tree has various different characteristics which are as follows:
• A tree is also known as a Recursive data structure.
• In a tree, the Height of the root can be defined as the longest path from the root
node to the leaf node.
• In a tree, one can also calculate the depth from the top to any node. The root node
has a depth of 0.
➢ Applications of Tree:
Different applications of Tree are as follows:
• Heap is a tree data structure that is implemented using arrays and used to implement
priority queues.
• B-Tree and B+ Tree are used to implement indexing in databases.
• Syntax Tree helps in scanning, parsing, generation of code, and evaluation of
arithmetic expressions in Compiler design.
• K-D Tree is a space partitioning tree used to organize points in K-dimensional space.
• Spanning trees are used in routers in computer networks.
➢ Operation performed on tree:
A tree is a non-linear data structure that consists of nodes connected by edges. Here
are some common operations performed on trees:
• Insertion: New nodes can be added to the tree to create a new branch or to increase
the height of the tree.
• Deletion: Nodes can be removed from the tree by updating the references of the
parent node to remove the reference to the current node.
• Search: Elements can be searched for in a tree by starting from the root node and
traversing the tree based on the value of the current node until the desired node is
found.
• Traversal: The elements in a tree can be traversed in several different ways, including
in-order, pre-order, and post-order traversal.
• Height: The height of the tree can be determined by counting the number of edges
from the root node to the furthest leaf node.
• Depth: The depth of a node can be determined by counting the number of edges
from the root node to the current node.
 • Balancing: The tree can be balanced to ensure that the height of the tree is
minimized and the distribution of nodes is as even as possible.

➢ Binary Tree:
• Binary tree is a tree data structure(non-linear) in which each node can
have at most two children which are referred to as the left child and
the right child.
• The topmost node in a binary tree is called the root, and the bottom-most
nodes are called leaves. A binary tree can be visualized as a hierarchical
structure with the root at the top and the leaves at the bottom.

➢ Representation of Binary Tree

Each node in a Binary Tree has three parts:
• Data
• Pointer to the left child
• Pointer to the right child
 ➢ Terminologies in Binary Tree
• Nodes: The fundamental part of a binary tree, where each node
contains data and link to two child nodes.
• Root: The topmost node in a tree is known as the root node. It has no parent and
serves as the starting point for all nodes in the tree.
• Parent Node: A node that has one or more child nodes. In a binary tree, each node
can have at most two children.
• Child Node: A node that is a descendant of another node (its parent).
• Leaf Node: A node that does not have any children or both children are null.
• Internal Node: A node that has at least one child. This includes all nodes except
the root and the leaf nodes.
• Depth of a Node: The number of edges from a specific node to the root node. The
depth of the root node is zero.
• Height of a Binary Tree: The number of nodes from the deepest leaf node to the root
node.
The diagram below shows all these terms in a binary tree.