4/1/25, 12:05 PM Evernote

UNIT 3. Programming and data structure

Data, Entity, Information, Difference between Data and Information, Data type ,
Build in data type, Abstract data type, Definition of data structures, Types of
Data Structures: Linear and Non-Linear Data Structure, Introduction to
Algorithms: Definition of Algorithms, Difference between algorithm and
programs, properties of algorithm, Algorithm Design Techniques, Performance
Analysis of Algorithms, Complexity of various code structures, Order of Growth,
Asymptotic Notations.

Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major

Order, and Column Major Order, Derivation of Index Formulae for 1-D,2-D Array
Application of arrays, Sparse Matrices and their representations. Recursion: recursion in
C, example of recursion, Tower of Hanoi Problem, simulating recursion, Backtracking,,
recursive algorithms, principles of recursion.

Array Implementation and Pointer Implementation of Singly Linked Lists, Doubly Linked
List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal,
Polynomial Representation and Addition Subtraction & Multiplications of Single variable

Abstract Data Type, Primitive Stack operations: Push & Pop, Array and Linked
Implementation of Stack in C, Application of stack: Prefix and Postfix Expressions,
Evaluation of postfix expression, Iteration and RecursionPrinciples of recursion, Tail
recursion, Removal of recursion Problem
solving using iteration and recursion with
examples such as binary search, Fibonacci numbers, and Hanoi towers.

Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and
linked implementation of queues in C, Dequeue and Priority Queue

Concept of Searching, Sequential search, Index Sequential Search, Binary Search.

Concept of Hashing & Collision resolution Techniques used in Hashing.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 1/57
4/1/25, 12:05 PM Evernote

Insertion Sort, Selection Sort, Bubble Sort, Heap Sort, Comparison of Sorting Algorithms,
Sorting in Linear Time: Counting Sort and Bucket Sort

Terminology used with Graph, Data Structure for Graph Representations: Adjacency
Matrices, Adjacency List, Adjacency. Graph Traversal: Depth First Search and Breadth
First Search, Connected Component.

Basic terminology used with Tree, Binary Trees, Binary Tree Representation: Array
Representation and Pointer (Linked List) Representation, Binary Search Tree, Complete
Binary Tree, A Extended Binary Trees, Tree Traversal algorithms: Inorder, Preorder and
Postorder, Constructing Binary Tree from given Tree Traversal, Operation of Insertion,
Deletion, Searching & Modification of data in Binary Search Tree. Threaded Binary trees,
Huffman coding using Binary Tree, AVL Tree and B Tree

DATA : A computer is primarily for processing data. A computer system considers

everything as data, be it instructions, pictures, songs, videos, documents, etc.

INFORMATION: Data can also be raw and unorganised facts that are processed to get
meaningful information.
ENTITY : entity is a unique, independent object in the real world that can be stored with
data

Distinct and unique data is known as an entity. An entity has some attributes which depict the entity's
characteristics.

DATE STRUCTURE
It is a particular way of organizing and storing data in a computer. So that it can be
accessed and modified efficiently. A data structure will have a collection of data and
functions or operations that can be applied on the data.

Abstract Data Type :

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 2/57
4/1/25, 12:05 PM Evernote

In computer science, an abstract data type (ADT) is a mathematical model for data types
where a data type is defined by its behavior (semantics) from the point of view of a user
of the data, specifically in terms of possible values, possible operations on data of this
type, and the behavior of these operations.

An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and
behaviours for a data type, without specifying how these operations are implemented or
how data is organized in memory.
The definition of ADT only mentions what operations are to be performed but not how
these operations will be implemented. It does not specify how data will be organized in
memory and what algorithms will be used for implementing the operations. It is called
“abstract” because it provides an implementation-independent view.

Note: ADT tells is WHAT is to be DONE and DATA structure tells us HOW to do it

Built-in Data Type Those data types for which a language has built-in support are known
as Built-in Data types.
For example, most of the languages provide the following built-in data types.
• Integers • Boolean (true, false) • Floating (Decimal numbers) • Character and Strings

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 3/57
4/1/25, 12:05 PM Evernote

Primitive Data Structures

1. Primitive Data Structures are the data structures consisting of the numbers and the
characters that come in-built into programs.
2. These data structures can be manipulated or operated directly by machine-level
instructions.
3. Basic data types like Integer, Float, Character, and Boolean come under the
Primitive Data Structures.
4. These data types are also called Simple data types, as they contain characters that
can't be divided further

Non-Primitive Data Structures

1. Non-Primitive Data Structures are those data structures derived from Primitive Data
Structures.
2. These data structures can't be manipulated or operated directly by machine-level
instructions.
3. The focus of these data structures is on forming a set of data elements that is either
homogeneous (same data type) or heterogeneous (different data types).
4. Based on the structure and arrangement of data, we can divide these data
structures into two sub-categories -

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 4/57
4/1/25, 12:05 PM Evernote

a. Linear Data Structures

b. Non-Linear Data Structures

Linear Data Structures

A data structure that preserves a linear connection among its data elements is known as
a Linear Data Structure.

The arrangement of the data is done linearly, where each element consists of the
successors and predecessors except the first and the last data element. However, it is
not necessarily true in the case of memory, as the arrangement may not be sequential.
Example:
1. ARRAYS
2. Linked LIST
3. STACKS
4. Queue

Based on memory allocation, the Linear Data Structures are further classified into two
types:

1. Static Data Structures: The data structures having a fixed size are known as Static
Data Structures. The memory for these data structures is allocated at the compiler
time, and their size cannot be changed by the user after being compiled; however,
the data stored in them can be altered.

The Array is the best example of the Static Data Structure as they have a fixed size,
and its data can be modified later.
2. Dynamic Data Structures: The data structures having a dynamic size are known as
Dynamic Data Structures. The memory of these data structures is allocated at the
run time, and their size varies during the run time of the code. Moreover, the user
can change the size as well as the data elements stored in these data structures at
the run time of the code.

Linked Lists, Stacks, and Queues are common examples of dynamic data structures

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 5/57
4/1/25, 12:05 PM Evernote

Non-Linear Data Structures

Non-Linear Data Structures are data structures where the data elements are not
arranged in sequential order. Here, the insertion and removal of data are not feasible in a
linear manner. There exists a hierarchical relationship between the individual data items.

Example : TREE,GRAPHS

ARRAYS

An array is a collection of items of the same variable type that are stored at contiguous
memory locations. It’s one of the most popular and simple data structures and is often
used to implement other data structures. Each item in an array is indexed starting with 0.
The key feature of the arrays to understand is that the data is stored in contiguous
memory locations, making it possible for the users to traverse through the data elements
of the array using their respective indexes.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 6/57
4/1/25, 12:05 PM Evernote

Declaration & Initialization of Array

GUAGE Declaration Initialization

C
Auto Auto

int arr[5]; int arr[] = { 1, 2, 3, 4, 5 };

int[] arr1 = new int [5];

Auto

int arr[];

Basic terminologies of Array

•
https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 7/57
4/1/25, 12:05 PM Evernote

Array Index :In an array, elements are identified by their indexes. Array index starts
from 0.
• Array element: Elements are items stored in an array and can be accessed by their
index.
• Array Length :The length of an array is determined by the number of elements it can
contain.

1. Fixed Sized Arrays:

We cannot alter or update the size of this array. Here only a fixed size (i,e. the size that is
mentioned in square brackets []) of memory will be allocated for storage. In case, we
don’t know the size of the array then if we declare a larger size and store a lesser
number of elements will result in a wastage of memory or we declare a lesser size than
the number of elements then we won’t get enough memory to store all the elements. In
such cases, static memory allocation is not preferred

2. Dynamic Sized Arrays:

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 8/57
4/1/25, 12:05 PM Evernote

The size of the array changes as per user requirements during execution of code so the
coders do not have to worry about sizes. They can add and removed the elements as per
the need. The memory is mostly dynamically allocated and de-allocated in these arrays.

Types of Arrays on the basis of Dimensions

1. One-dimensional Array(1-D Array): You can imagine a 1d array as a row, where elements are stored one
after another.

2. Multi-dimensional Array: A multi-dimensional array is an array with more than one dimension. We can
use multidimensional array to store complex data in the form of tables, etc. We can have 2-D arrays, 3-D
arrays, 4-D arrays and so on.
Two-Dimensional Array(2-D Array or Matrix): 2-D Multidimensional arrays can be considered as an array
of arrays or as a matrix consisting of rows and columns

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 9/57
4/1/25, 12:05 PM Evernote

Three-Dimensional Array(3-D Array): A 3-D Multidimensional array contains three dimensions, so it can
be considered an array of two-dimensional arrays

Calculating the address of any element In the 1-D array:

Address of A[Index] = B + W * (Index – LB)

Where:
• Index = The index of the element whose address is to be found (not the value of the
element).
• B = Base address of the array.
• W = Storage size of one element in bytes.
• LB = Lower bound of the index (if not specified, assume zero)

Example: Given the base address of an array A[1300 ………… 1900] as 1020 and the size of each element
is 2 bytes in the memory, find the address of A[1700].
Given:
• Base address (B) = 1020
• Lower bound (LB) = 1300
• Size of each element (W) = 2 bytes
• Index of element (not value) = 1700
Formula used:
Address of A[Index] = B + W * (Index – LB)
Address of A[1700] = 1020 + 2 * (1700 – 1300)
= 1020 + 2 * (400)
= 1020 + 800

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 10/57
4/1/25, 12:05 PM Evernote

Address of A[1700] = 1820

Calculate the address of any element in the 2-D array:

The 2-dimensional array can be defined as an array of arrays. The 2-Dimensional arrays are
organized as matrices which can be represented as the collection of rows and columns as array[M]
[N] where M is the number of rows and N is the number of columns

To find the address of any element in a 2-Dimensional array there are the following two ways-

1. Row Major Order

2. Column Major Order
1. Row Major Order:
Row major ordering assigns successive elements, moving across the rows and then down the next row, to
successive memory locations.

In simple language, the elements of an array are stored in a Row-Wise fashion.To find the address of the
element using row-major order uses the following formula:

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 11/57
4/1/25, 12:05 PM Evernote

Example: Given an array, arr[1………10][1………15] with base value 100 and the size of each element is 1
Byte in memory. Find the address of arr[8][6] with the help of row-major order

2. Column Major Order:

If elements of an array are stored in a column-major fashion means moving across the column and then to
the next column then it’s in column-major order. To find the address of the element using column-major
order use the following formula:

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 12/57
4/1/25, 12:05 PM Evernote

Sparse Matrices and their representations:

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 13/57
4/1/25, 12:05 PM Evernote

Basic Operations in Arrays

• Traverse− print all the array elements one by one.

• Insertion− Adds an element at the given index.
• Deletion− Deletes an element at the given index.
• Search− Searches an element using the given index or by the value.
• Update− Updates an element at the given index.
• Display− Displays the contents of the array.

1. Traversal: is one of the fundamental operations in data structures, involving visiting

each element systematically. In the context of arrays, traversal means accessing
each element from the beginning to the end of the array. This operation is crucial for
various tasks such as searching, updating, and processing data.

Recursion

The process in which a function calls itself directly or indirectly is called recursion and
the corresponding function is called a recursive function.

• A recursive algorithm takes one step toward solution and then recursively call itself to
further move. The algorithm stops once we reach the solution.
• Since called function may further call itself, this process might continue forever. So it
is essential to provide a base case to terminate this recursion process.
Need of Recursion:

• Recursion helps in logic building. Recursive thinking helps in solving complex

problems by breaking them into smaller subproblems.
• Recursive solutions work as a a basis for Dynamic Programming and Divide and
Conquer algorithms.
• Certain problems can be solved quite easily using recursion like Towers of Hanoi
(TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.

Pointer
https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 14/57
4/1/25, 12:05 PM Evernote

A pointer is a variable that stores the memory address of another variable. Instead of
holding a direct value, it holds the address where the value is stored in memory
or
A pointer is a variable that stores the memory address of another variable as its value.

Linked Lists

Linked list is a linear data structure that contains sequence of elements such that each
element links to its next element in the sequence. Each element in a linked list is called as
"Node"

Linked List is a very commonly used linear data structure which consists of set of nodes
in a sequence.
A linked list is the most sought-after data structure when it comes to handling dynamic
data elements.

A pointer variable called START or FIRST which contains the address of the first node. A special case is the
list that has no nodes, such a list is called the null list or empty list and is denoted by the null pointer in the
variable START.

REPRESENTATION OF LINKED LISTS IN MEMORY

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 15/57
4/1/25, 12:05 PM Evernote

Let LIST be a linked list. Then LIST will be maintained in memory as follows.
1. LIST requires two linear arrays such as INFO and LINK-such that INFO[K] and LINK[K]
contains the information part and the NeXT pointer field of a node of LIST.
2. LIST also requires a variable name such as START which contains the location of the beginning of the
list, and a NeXT pointer sentinel denoted by NULL-which indicates the end of the list.
3. The subscripts of the arrays INFO and LINK will be positive, so choose NULL = 0, unless otherwise
stated

Garbage Collection
Suppose some memory space becomes reusable because a node is deleted from a list
or an entire list is deleted from a program. So space is need to be available for future use.

One way to bring this is to immediately reinsert the space into the free-storage list.
However, this method may be too time-consuming for the operating system of a
computer, which may choose an alternative method, as follows.
The operating system of a computer may periodically collect all the deleted space onto
the freestorage list. Any technique which does this collection is called garbage
collection.
Garbage collection takes place in two steps.
1. First the computer runs through all lists, tagging those cells which are currently in use

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 16/57
4/1/25, 12:05 PM Evernote

2. And then the computer runs through the memory, collecting all untagged space onto
the free-storage list

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 17/57
4/1/25, 12:05 PM Evernote

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 18/57
4/1/25, 12:05 PM Evernote

The complexity of this algorithm for the worst-case running time is proportional to the number n of
elements in LIST, and the average-case running time is approximately proportional to n/2 (with the
condition that ITEM appears once in LIST but with equal probability in any node of LIST

The complexity of this algorithm for the worst-case running time is proportional to the number n of
elements in LIST, and the average-case running time is approximately proportional to n/2

DETAIL NOTES ON LINKED LIST PDF ;

linked list pdf.pdf 1 of 28 pages •

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 19/57
4/1/25, 12:05 PM Evernote

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 20/57
4/1/25, 12:05 PM Evernote

Stack Data Structure

Stack is a linear data structure that follows LIFO (Last In First Out) Principle, the last
element inserted is the first to be popped out. It means both insertion and deletion
operations happen at one end only.

Types of Stack:
• 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.

Basic Operations on Stack:

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 21/57
4/1/25, 12:05 PM Evernote

In order to make manipulations in a stack, there are certain operations provided to us.

• push() to insert an element into the stack

• pop() to remove an element from the stack
• top() Returns the top element of the stack.
• isEmpty() returns true if stack is empty else false.
• isFull() returns true if the stack is full else false.

Push Operation on Stack

Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.

Algorithm for Push Operation:

• Before pushing the element to the stack, we check if the stack is full .
• If the stack is full (top == capacity-1) , then Stack Overflows and we cannot insert the
element to the stack.
• Otherwise, we increment the value of top by 1 (top = top + 1) and the new value is
inserted at top position .
• The elements can be pushed into the stack till we reach the capacity of the stack.

Pop Operation in Stack

Removes an item from the stack. The items are popped in the reversed order in which
they are pushed. If the stack is empty, then it is said to be an Underflow condition.

Algorithm for Pop Operation:

• Before popping the element from the stack, we check if the stack is empty .
• If the stack is empty (top == -1), then Stack Underflows and we cannot remove any
element from the stack.
• Otherwise, we store the value at top, decrement the value of top by 1 (top = top – 1)
and return the stored top value

Algorithm for isEmpty Operation :

• Check for the value of top in stack.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 22/57
4/1/25, 12:05 PM Evernote

• If (top == -1) , then the stack is empty so return true .

• Otherwise, the stack is not empty so return false .

Algorithm for isFull Operation:

• Check for the value of top in stack.

• If (top == capacity-1), then the stack is full so return true .
• Otherwise, the stack is not full so return false.

Implement Stack using Array

To implement a stack using an array, initialize an array and treat its end as the stack’s
top. Implement push (add to end), pop (remove from end), and peek (check end)
operations, handling cases for an empty or full stack.

Step-by-step approach:

1. Initialize an array to represent the stack.

2. Use the end of the array to represent the top of the stack.
3. Implement push (add to end), pop (remove from the end), and peek (check end)
operations, ensuring to handle empty and full stack conditions

Infix, Prefix, Postfix

Infix Expressions:

Infix expressions are mathematical expressions where the operator is placed between
its operands. This is the most common mathematical notation used by humans. For
example, the expression "2 + 3" is an infix expression, where the operator "+" is placed
between the operands "2" and "3".

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 23/57
4/1/25, 12:05 PM Evernote

Infix notation is easy to read and understand for humans, but it can be difficult for
computers to evaluate efficiently. This is because the order of operations must be taken
into account, and parentheses can be used to override the default order of operations.

Prefix Expressions (Polish Notation)

Prefix expressions are also known as Polish notation, are a mathematical notation where the operator
precedes its operands. This differs from the more common infix notation, where the operator is placed
between its operands.

In prefix notation, the operator is written first, followed by its operands. For example, the infix expression "a
+ b" would be written as "+ a b" in prefix notation

Postfix Expressions (Reverse Polish Notation)

Postfix expressions are also known as Reverse Polish Notation (RPN), are a mathematical notation where
the operator follows its operands. This differs from the more common infix notation, where the operator is
placed between its operands.

In postfix notation, operands are written first, followed by the operator. For example, the infix expression "5
+ 2" would be written as "5 2 +" in postfix notation

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 24/57
4/1/25, 12:05 PM Evernote

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 25/57
4/1/25, 12:05 PM Evernote

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 26/57
4/1/25, 12:05 PM Evernote

Queue

Queue is a linear data structure that follows FIFO (First In First Out) Principle, so the first
element inserted is the first to be popped out.
FIFO Principle in Queue:
FIFO Principle states that the first element added to the Queue will be the first one to be
removed or processed.

Basic Terminologies of Queue

• Front: Position of the entry in a queue ready to be served, that is, the first entry that will be removed
from the queue, is called the front of the queue. It is also referred as the head of the queue.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 27/57
4/1/25, 12:05 PM Evernote

• Rear: Position of the last entry in the queue, that is, the one most recently added, is called the rear of
the queue. It is also referred as the tail of the queue.
• Size:Size refers to the current number of elements in the queue.
• Capacity: Capacity refers to the maximum number of elements the queue can hold.
• isFull() – Validates if the queue is full.
• isEmpty() – Checks if the queue is empty.

Operations on Queue
1. Enqueue:
Enqueue operation adds (or stores) an element to the end of the queue.
Steps:
1. Check if thequeue is full. If so, return an overflowerror and exit.
2. If the queue is not full, increment the rear pointer to the next available position.
3. Insert the element at the rear.

Complexity Analysis:
Time Complexity: O(1)
Space Complexity: O(N)
2. Dequeue:
Dequeue operation removes the element at the front of the queue. The following steps
are taken to perform the dequeue operation:

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 28/57
4/1/25, 12:05 PM Evernote

1. Check if the queue is empty. If so, return an underflow error.

2. Remove the element at the front.
3. Increment the front pointer to the next element.

Types of Queues:

There are five different types of queues that are used in different scenarios. They are:

1. Input Restricted Queue (this is a Simple Queue)

2. Output Restricted Queue (this is also a Simple Queue)
3. Circular Queue
4. Double Ended Queue (Deque)
5. Priority Queue
• Ascending Priority Queue
• Descending Priority Queue

CIRCULAR QUEUE

circular queue is the extended version of a regular queue where the last element is connected to the
first element. Thus forming a circle-like structure
• The circular queue solves the major limitation of the normal queue. In a normal queue, after a bit of
insertion and deletion, there will be non-usable empty space.
•

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 29/57
4/1/25, 12:05 PM Evernote

PRIORITY QUEUE :
A priority queue is a type of queue that arranges elements based on their priority values.
Elements with higher priority values are typically retrieved or removed before elements
with lower priority values. Each element has a priority value associated with it. When we
add an item, it is inserted in a position based on its priority value.

There are several ways to implement a priority queue, including using an array, linked list,
heap, or binary search tree, binary heap being the most common method to implement.
The reason for using Binary Heap is simple, in binary heaps, we have easy access to the
min (in min heap) or max (in max heap) and binary heap being a complete binary tree are
easily implemented using arrays. Since we use arrays, we have cache friendliness
advantage also.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 30/57
4/1/25, 12:05 PM Evernote

Arrays enqueue() dequeue() peek()

Time Complexity O(1) O(n) O(n)

NON LINEAR DATA STRUCTURE :

Data structures where data elements are not arranged sequentially or linearly are called
non-linear data structures. In a non-linear data structure, single level is not involved.
Therefore, we can’t traverse all the elements in single run only.
Non-linear data structures are not easy to implement in comparison to linear data
structure. It utilizes computer memory efficiently in comparison to a linear data structure.
Its examples are trees and graphs.

Tree data structureis a hierarchical structure that is used to represent and organize data
in the form of parent child relationship. The following are some real world situations
which are naturally a tree.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 31/57
4/1/25, 12:05 PM Evernote

• Folder structure in an operating system.

• Tag structure in an HTML (root tag the as html tag) or XML document

Basic Terminologies In Tree Data Structure:

• Parent Node:The node which is an immediate predecessor of a node is called the
parent node of that node.{B}is the parent node of {D, E}.

• Child Node:The node which is the immediate successor of a node is called the child
node of that node. Examples: {D, E}are the child nodes of {B}.

• Root Node:The topmost node of a tree or the node which does not have any parent
node is called the root node. {A}is the root node of the tree. A non-empty tree must
contain exactly one root node and exactly one path from the root to all other nodes of
the tree.

• Leaf Node or External Node: The nodes which do not have any child nodes are called
leaf nodes. {I, J, K, F, G, H}are the leaf nodes of the tree.

• Ancestor of a Node: Any predecessor nodes on the path of the root to that node are
called Ancestors of that node.{A,B}are the ancestor nodes of the node{E}

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 32/57
4/1/25, 12:05 PM Evernote

Descendant: A node x is a descendant of another node y if and only if y is an

ancestor of x.

• Sibling: Children of the same parent node are called siblings.{D,E}are called siblings.

• Level of a node: The count of edges on the path from the root node to that node. The
root node has level 0.
• Internal node: A node with at least one child is called Internal Node.

• Neighbour of a Node: Parent or child nodes of that node are called neighbors of that
node.

• Subtree: Any node of the tree along with its descendant.

Types of Tree
General Tree
• Binary Tree
• Binary Search Tree
• AVL Tree
• Red-Black Tree
• N-ary Tree

1. BINAR TREE :
A Binary Tree Data Structure is a hierarchical data structure in which each node has at
most two children, referred to as the left child and the right child.
It is commonly used in computer science for efficient storage and retrieval of data, with
various operations such as insertion, deletion, and traversal.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 33/57
4/1/25, 12:05 PM Evernote

Representation of Binary Tree

Each node in a Binary Tree has three parts:

• Data
• Pointer to the left child
• Pointer to the right child

If a node has one child, it is called a unary node. If a node has two children, it is called a binary node.

Properties of Binary Tree

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 34/57
4/1/25, 12:05 PM Evernote

1. The maximum number of nodes at level ‘l’ of a binary tree is 2l:

2. The Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1

3. In a Binary Tree with N nodes, the minimum possible height or the minimum
number of levels is Log2(N+1):

4. A Binary Tree with L leaves has at least | Log2L |+ 1 levels

5. In a Binary tree where every node has 0 or 2 children, the number of leaf nodes
is always one more than nodes with two children

6. In a non-empty binary tree, if n is the total number of nodes and e is the total
number of edges, then e = n-1:

Types of Binary Tree

Full Binary Tree
A Binary Tree is a full binary tree if every node has 0 or 2 children. The following are examples of a full
binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaf nodes have two
children.

Degenerate (or pathological) tree

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 35/57
4/1/25, 12:05 PM Evernote

A Tree where every internal node has one child. Such trees are performance-wise same as linked list. A
degenerate or pathological tree is a tree having a single child either left or right.

Skewed Binary Tree

A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left
nodes or the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and
right-skewed binary tree

Types of Binary Tree On the basis of the completion of levels:

1. Complete Binary Tree
2. Perfect Binary Tree
3. Balanced Binary Tree
https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 36/57
4/1/25, 12:05 PM Evernote

1. Complete Binary Tree

A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last
level and the last level has all keys as left as possible.

A complete binary tree is just like a full binary tree, but with two major differences:
• Every level except the last level must be completely filled.
• All the leaf elements must lean towards the left.
• The last leaf element might not have a right sibling i.e. a complete binary tree doesn’t have to be a
full binary tree.

2. Perfect Binary Tree

A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes
are at the same level. The following are examples of Perfect Binary Trees.

A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and
all the leaf nodes are at the same level.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 37/57
4/1/25, 12:05 PM Evernote

NOTE : In a Perfect Binary Tree, the number of leaf nodes is the number of internal nodes plus 1 ( L = I +
1)

. Balanced Binary Tree

A binary tree is balanced if the height of the tree is O(Log n) where n is the number of
nodes. For Example, the AVL tree maintains O(Log n) height by making sure that the
difference between the heights of the left and right subtrees is at most 1. Red-Black trees
maintain O(Log n) height by making sure that the number of Black nodes on every root to
leaf paths is the same and that there are no adjacent red nodes. Balanced Binary Search
trees are performance-wise good as they provide O(log n) time for search, insert and
delete.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 38/57
4/1/25, 12:05 PM Evernote

It is a type of binary tree in which the difference between the height of the left and the right subtree for
each node is either 0 or 1. In the figure above, the root node having a value 0 is unbalanced with a depth of
2 units.

Representation of Binary Trees

There are two primary ways to represent binary trees:

1. Linked Node Representation

2. Array Representation

Disadvantages:

• Needs extra memory for pointers.

• Finding a node can take longer because you have to start from the root and follow pointers.

// Node structure of each node of the binary tree.

struct Node {
int data;
https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 39/57
4/1/25, 12:05 PM Evernote

struct Node* left;

struct Node* right;
};

// Note : Unlike other languages, C does not support

// Object Oriented Programming. So we need to write
// a separat method for create and instance of tree node
struct Node* createNode(int val) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Node structure of each node of the binary tree.

class Node {
int data;
Node left, right;

Node(int val) {
data = val;
left = null;
right = null;
}
}

2. Array Representation
Array Representation is another way to represent binary trees, especially useful
when the tree is complete (all levels are fully filled except possibly the last, which is
filled from left to right). In this method:
• The tree is stored in an array.
• For any node at index i:
◦ Left Child: Located at 2 * i + 1

◦ Right Child: Located at 2 * i + 2

• Root Node: Stored at index 0

•
https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 40/57
4/1/25, 12:05 PM Evernote

•
Advantages:

• Easy to navigate parent and child nodes using index calculations, which is fast
• Easier to implement, especially for complete binary trees.
Disadvantages:

• You have to set a size in advance, which can lead to wasted space.
• If the tree is not complete binary tree then then many slots in the array might be empty, this will result
in wasting memory
• Not as flexible as linked representations for dynamic trees.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 41/57
4/1/25, 12:05 PM Evernote

Binary Search Tree :

A Binary Search Tree (or BST) is a data structure used in computer science for
organizing and storing data in a sorted manner. Each node in a Binary Search Tree has at
most two children, a left child and a right child, with the left child containing values less
than the parent node and the right child containing values greater than the parent node.
This hierarchical structure allows for efficient searching, insertion, and deletion
operations on the data stored in the tree.

Properties of Binary Search Tree:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes(BST may have duplicate values with different handling approaches).

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 42/57
4/1/25, 12:05 PM Evernote

Tree Traversal Techniques :

Tree Traversal techniques include various ways to visit all the nodes of the tree. Unlike
linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one
logical way to traverse them, trees can be traversed in different ways.

visiting or accessing each node of the tree exactly once in a certain order. Tree traversal
algorithms help us to visit and process all the nodes of the tree

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 43/57
4/1/25, 12:05 PM Evernote

1. Inorder traversal visits the node in the order: Left -> Root -> Right

Uses of Inorder Traversal:

• In the case of binary search trees (BST), Inorder traversal gives nodes in non-
decreasing order.
• To get nodes of BST in non-increasing order, a variation of Inorder traversal where
Inorder traversal is reversed can be used.
• Inorder traversal can be used to evaluate arithmetic expressions stored in expression
trees.

Preorder Traversal:

Preorder traversal visits the node in the order: Root -> Left -> Right

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 44/57
4/1/25, 12:05 PM Evernote

Algorithm for Preorder Traversal:

Preorder(tree)

• Visit the root.

• Traverse the left subtree, i.e., call Preorder(left->subtree)
• Traverse the right subtree, i.e., call Preorder(right->subtree)

Uses of Preorder Traversal:

• Preorder traversal is used to create a copy of the tree.

• Preorder traversal is also used to get prefix expressions on an expression tree.

Postorder Traversal:
Postorder traversal visits the node in the order: Left -> Right -> Root

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 45/57
4/1/25, 12:05 PM Evernote

Algorithm Postorder(tree)
• Traverse the left subtree, i.e., call Postorder(left->subtree)
• Traverse the right subtree, i.e., call Postorder(right->subtree)
• Visit the root

Uses of Postorder Traversal:

• Postorder traversal is used to delete the tree. See the question for the deletion of a tree for details.
• Postorder traversal is also useful to get the postfix expression of an expression tree.
• Postorder traversal can help in garbage collection algorithms, particularly in systems where manual
memory management is used.

Complete Binary Tree :

A complete binary tree is a binary tree in which all the levels are completely filled except
possibly the lowest one, which is filled from the left.
A complete binary tree is just like a full binary tree, but with two major differences

1. All the leaf elements must lean towards the left.

2. The last leaf element might not have a right sibling i.e. a complete binary tree
doesn't have to be a full binary tree.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 46/57
4/1/25, 12:05 PM Evernote

Full Binary Tree vs Complete Binary Tree

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 47/57
4/1/25, 12:05 PM Evernote

Extended binary tree

Extended binary tree is a type of binary tree in which all the null sub tree of the original tree are replaced
with special nodes called external nodes whereas other nodes are called internal nodes

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 48/57
4/1/25, 12:05 PM Evernote

NOTE : BINARY TREE NOTED PDF

202003251324427012himanshu_ Binary_Trees.pdf 1 of 54 pages •

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 49/57
4/1/25, 12:05 PM Evernote

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 50/57
4/1/25, 12:05 PM Evernote

Constructing Binary Tree from given Tree Traversal :

Terminologies of Graphs in Data Structures

• An edge is one of the two primary units used to form graphs. Each edge has
two ends, which are vertices to which it is attached.

• If two vertices are endpoints of the same edge, they are adjacent.

• A vertex's outgoing edges are directed edges that point to the origin.

• A vertex's incoming edges are directed edges that point to the vertex's
destination.

• The total number of edges occurring to a vertex in a graph is its degree.

• The out-degree of a vertex in a directed graph is the total number of

outgoing edges, whereas the in-degree is the total number of incoming
edges.

• A vertex with an in-degree of zero is referred to as a source vertex, while

one with an out-degree of zero is known as sink vertex.

• An isolated vertex is a zero-degree vertex that is not an edge's endpoint.

• A path is a set of alternating vertices and edges, with each vertex connected
by an edge.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 51/57
4/1/25, 12:05 PM Evernote

• The path that starts and finishes at the same vertex is known as a cycle.

• A path with unique vertices is called a simple path.

• For each pair of vertices x, y, a graph is strongly connected if it contains a

directed path from x to y and a directed path from y to x.
• A directed graph is weakly connected if all of its directed edges are replaced
with undirected edges, resulting in a connected graph. A weakly linked
graph's vertices have at least one out-degree or in-degree.

• A tree is a connected forest. The primary form of the tree is called a rooted
tree, which is a free tree.
• A spanning subgraph that is also a tree is known as a spanning tree.
• A connected component is the unconnected graph's most connected
subgraph.

• A bridge, which is an edge of removal, would sever the graph.

• Forest is a graph without a cycle.

Representation of Graphs in Data Structures

• Adjacency matrix
• Adjacency list

Adjacency Matrix

• A sequential representation is an adjacency matrix.

• It's used to show which nodes are next to one another. I.e., is there any connection between nodes in a
graph?
https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 52/57
4/1/25, 12:05 PM Evernote

• You create an MXM matrix G for this representation. If an edge exists between vertex a and vertex b,
the corresponding element of G, gi,j = 1, otherwise gi,j = 0.
• If there is a weighted graph, you can record the edge's weight instead of 1s and 0s.

Undirected Graph Representation

Directed Graph Representation

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 53/57
4/1/25, 12:05 PM Evernote

Weighted Undirected Graph Representation

Weight or cost is indicated at the graph's edge, a weighted graph representing these values in the matrix.

GRAPH notes PDF

graph DS notes.pdf 1 of 14 pages •

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 54/57
4/1/25, 12:05 PM Evernote

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 55/57
4/1/25, 12:05 PM Evernote

SEARCHING

Searching is a process of finding a particular record, which can be a single element or a small
chunk, within a huge amount of data. The data can be in various forms: arrays, linked lists, trees,
heaps, and graphs etc. With the increasing amount of data nowadays, there are multiple techniques
to perform the searching operation.
• Sequential Searching
• Interval Searching

Sequential Searching :

the sequential searching operation traverses through each element of the data
sequentially to look for the desired data. The data need not be in a sorted manner for
this type of search
Example − Linear Search

Interval Searching
Unlike sequential searching, the interval searching operation requires the data
to be in a sorted manner. This method usually searches the data in intervals; it
could be done by either dividing the data into multiple sub-parts or jumping
through the indices to search for an element.

Example − Binary Search, Jump Search etc.

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 56/57
4/1/25, 12:05 PM Evernote

https://lite.evernote.com/note/145a31f5-95eb-d788-85fb-66ff325b8955 57/57