python &

DATA STRUCTURES

50
CARDS
 INDEX
Variables 5

Type Keyword 7

For Loops 9

Sorting 11

Functions 13

Arguments 15

Keyword Arguments 17

Lamda Functions 19

Lists 21

Strings 23

Sets 25

Dictionaries 27

Conditional Statements 29

While Loop 31

Classes & Objects 33

Python Math 35

Try Except Block 37

List Comprehensions 39

Map Function 41
Casting 43

Tuples 45

Tuple Unpacking 47

Zip Keyword 49

Enumerate Function 51

Open Function 53

Recursion 55

Singly Linked List 57

Doubly Linked List 59

Stack 61

Queue 63

Tree 65

Binary Search Tree 67

Trie 69

Heap 71

Heapify 73

Priority Queue 75

Hashing 77

Hash Map 79
Selection Sort 81

Quick Sort 83

Merge Sort 85

Breadth First Search 87

Depth First Search 89

Graph 91

B - Trees 93

B + Trees 95

Advanced Algorithms 97

Greedy Algorithms 99

Runtime Analysis 101

Array Sorting Algorithms 103

Variables

5
 Variab le s

Python has no keyword for declaring a variable and the data type
doesn’t have to be specified as well. It is automatically inferred
from the value you specify:

A variable is created the moment you first assign a value to it.

Python is a dynamically typed language and this is a
consequence of that
 Type
keyword

7
 Type ke y wor d

type() method returns the class type of the variable that is

passed. type() function is mostly used for debugging purposes.

The type() function either returns the type of the object or

returns a new type object based on the arguments passed

Example:
 For
Loops

9
 Fo r Lo op s

It is a loop that is used to iterate a data structure. The data

structure can be a list, string or dictionary.
Loop continues until we reach the last item in the sequence.
The body of a for loop is separated from the rest of the code
using indentation.

Lists:

Strings: Range Function:

Dictionaries:
 <
Sorting

11
< So rt i ng

The sort() method sorts the elements of a given list in either an

ascending or descending order.

By default, sort() doesn't require any extra parameters. However,

it has two optional parameters:

reverse - If True, the sorted list is reversed (or sorted in

<
Descending order)
key - function that serves as a key for the sort comparison
Example:

To sort the list in descending order, a parameter reverse=True is

passed as shown in the below code snippet.
< <
Functions

13
< <
F uncti ons

Functions are predefined tasks that the creator writes to call

upon later.

Functions help break our program into smaller and modular

chunks.

Think of it in this way: You can write code to create a square, put
it in a function, and instead of teaching the computer how to
create a square every time, you can just call upon the original
function.

Writing a function consists of two main things: Creating the

function and then calling the function.

In Python a function is defined using the def keyword:

To let a function return a value, we use the return statement

Example:
< <
Arguments

15
<
A rg u me nts

Arguments:
Information can be passed into functions as arguments.
Arguments are specified after the function name, inside the
parentheses. We can add as many arguments as we want. They
need to be separated with a comma.
Example:

Arbitrary Arguments (*args):

If we are not aware of how many arguments will be passed into
the function, then an asterisk (*) is added before the parameter
name in the function definition. Python allows us to handle this
kind of situation through function calls with an arbitrary number
of arguments.

This way the function will receive a tuple of arguments and can
access the items accordingly.
Example:
 <
Keyword
Arguments

17
<
Keyword Arguments

Keyword Arguments:
Arguments can also be passed with the key = value syntax. This
way the order of the arguments does not matter

KEYS VALUES

‘a’ ‘alpha’

‘o’ ‘omega’

‘g’ ‘gamma’

Arbitrary Keyword Arguments:

If we are not aware of how many keyword arguments will be
passed into the function, then two asterisks: (**) are added
before the parameter name in the function definition.

This way the function will receive a dictionary of arguments, and

can access the items accordingly:
 <
Lambda
Functions

19
<
La mbda Funct i ons

A lambda function is a small anonymous function. A lambda

function can take any number of arguments, but can only have
one expression.

We use lambda functions when we require a nameless function

for a short period of time. Simply put, a lambda function is just
like any normal python function, except that it has no name
when defining it, and it is contained in one line of code.

You can use lambda functions when you have a very simple one
line expression. This way you can make the code look much
cleaner.

Syntax → lambda arguments : expression

The keyword lambda must come first. A full colon (:) separates
the argument and the expression.

The expression is executed and the result is returned

In the example code below, a is the argument and a+10 is the

expression.

In the example code below, a, b are the arguments and a * b

is the expression.
 <
Lists

21
<
L ists

Lists are used to store multiple items in a single variable. The items
in a list can be of any data type.

To create a list, the elements are placed inside square brackets

“[]”, separated by commas. As shown above, lists can contain
elements of different types as well as duplicated elements.

List items are indexed, the first item has index 0, the second item
has index 1, etc

Accessing an item from a list:

If you add new items to a list, the new items will be placed at
the end of the list
List Appending:

List deletion:
The remove() method removes the specified item.
 <
Strings

23
<
St r i ngs

A String can be a collection of alphabets, words, or other

characters. They are typically used to store values like names,
places or any other combination of alphanumeric or special
characters

Strings in Python are "immutable" which means they cannot be

changed after they are created. You cannot insert or remove a
character from a string after it is created.

Strings in python are surrounded by either single quotation marks

or double quotation marks.

Syntax:

String Length:

String concatenation:
 <
SETS

25
<
SE TS

Sets are used to store multiple items in a single variable just like a
list but they cannot have duplicate values. To create a Set,
elements are placed inside curly braces “{}”.
A few characteristics of Sets:

• Sets do not have a proper order. The items in a set are arranged
in a random order.
• Sets are unchangeable. Meaning that once a Set is created, you
cannot add or remove items from it.
• The items in a Set do not have an index.
• Sets cannot have two items with the same value
• Sets are used when you want to store a set of unique values and
perform venn diagram like operations on it for example union,
intersection etc
Sets cannot have duplicates as illustrated below
 <
Dictionaries

27
<
D ict iona r i e s

Dictionaries are used to store data in key:value pairs, unlike other

data types (list, set etc) where you usually hold only a single
value as an element.

In Python a dictionary can be created with curly braces “{}”,

separated by a comma.

Few characteristics of Dictionaries:

•The items in a dictionary follow a proper order.
•A dictionary is changeable, which means that you can still add or
remove items from a dictionary after creating it.
•A dictionary does not allow duplicates.

Dictionary items are presented in key:value pairs,as shown below.

Example:
 <
Conditional
Statements

29
<
C o ndi ti o n a l
Stat e m e n tS

Conditional statements in Python are used to perform different

computations based on whether an expression/value evaluates
to True or False.

if keyword:
In this example, we use two variables, a and b, which are used as
part of the if statement to test whether b is greater than a. As a
is100, and b is 33 we know that 100 is greater than 33, and so we
print that "a is greater than b"

elif keyword:
The elif keyword in python is used to execute a condition if the
previous conditions weren’t true. It's basically a way of saying
that "if the previous conditions were not true, then try this
condition".
else keyword:
If the previous if and elif condition fails, then the else keyword is
used.

Example:
 <
WHILE
LOOP

31
<
WH IL E LO OP

While Loops:
With the while loop, we can execute a set of statements as long
as a condition is true.

Break Statement:
With the break statement we can stop the loop even if the while
condition is true:

Continue Statement:
With the continue statement we can stop the current iteration,
and continue with the next:
 <
Classes
and
Objects

33
<
C las se s and Ob jects

Classes and Objects:

Since Python is an object oriented Programming language, almost
everything in python is an object with its own set of attributes
and methods. A Class is an object constructor or a blueprint for
creating objects

The __init__() function:

While initiating a class in python, we need to have a function
called __init__() that needs to be executed first.

In the __init__() class, assign basic attributes that you want the
class to have for example you can have ‘student_name’, ‘roll no’,
‘grade’ as attributes for class named ‘Student’

Use the __init__() function to assign values to object properties,

or other operations that are necessary to do when the object is
being created:
 <
Python
Math

35
<
Pyth on Math

Python has a set of in built math functions which allows you to

perform math functions on numbers

min() and max() functions:

The min() and max() functions can be used to find the lowest or
highest value in an iterable:

Note: iterable in python can mean anything that you can loop
over and has a list of contents for example list, tuple, set etc

abs() function:
The abs() function returns the absolute (positive) value of the
specified number

pow() function:
The pow(x, y) function returns the value of x to the power of y
(xy)
 <
Try Except
Blocks

37
<
T ry Exc ept B lo cks

Try Except Blocks are used to catch exceptions in Python. The

code is divided into two blocks: Try block and an Exception Block.

The Try block is used to test a block of code and if there’s an error
the Exception block is used to handle it.

Typically a try except block is used when you are unsure if an

exception would come up. You are basically trying to ensure that
a piece of code works, but in the exception that it doesn’t work,
the except block handles the error peacefully and your program
does not crash and moves on to the next block of code.

It's a good practice to use Try Except blocks whenever you can.

Example:
The try block will generate an exception, because x is not defined,
therefore the code execution moves onto the except block

Else Keyword:
You can use the else keyword to define a block of code to be
executed if no errors were raised:
 <
List
Comprehensions

39
<
L i st C o mpre he nsi ons

List Comprehensions:
List comprehension offers a shorter syntax when you want to
create a new list based on the values of an existing list.

You can use it make your code look cleaner and more professional
It also enhances the readability for the programmer

Syntax:

Example:
 <
Map
Function

41
<
M ap F unct i on

When you want to apply a function over each element of an

iterable(list, tuple, set etc.), you can use the map() function. The
map() function returns an iterable object after the function has
been applied onto the input.
Syntax:

Function: It is a function to which map passes each element of

a given iterable

Iterable: It is a data structure which is to be mapped, can be

a list, tuple, set ect

In the above code example, we pass two parameters to the map()

function.

A calculateLength function, that returns the length of an iterable

and A tuple fruits.

The calculateLength function runs on each item of the tuple fruits

and returns the item's length.

The lengths of these items are stored in a variable called

lengthOfItems.

To print this variable, we first have to convert it to a list. Hence

list(lengthOfItems) returns the lengths of the items in a list.
 <
Casting

43
<
Casti ng

If you want to specify the data type of a variable, this can be

done with casting.

You can overwrite the default data type with the data type of
your choice, however you can try to convert something like ‘Messi’
into an int data type, that will throw an error
 <
Tuples

45
<
Tup le s

A tuple is similar to a list but the main difference is that it’s

immutable once it’s created. You cannot add or remove items in
a tuple once you create it.

They are usually created to restrict any changes to the data

stored inside and also when you want it to stay intact throughout
the program It can be indexed just like a list and can have
duplicates. It can hold multiple data types as well.

To create a Tuple, elements are placed inside these circular

braces ()

Creating a tuple:

Tuple Length:

Accessing tuple elements:

 <
Tuple
Unpacking

47
<
T u pl e Un packi ng

We can assign each element of a tuple to a separate variable in

python. This is called Tuple unpacking.

This is usually used when you are calling multiple values from a
function or when you have individual use case for each variable
that is extracted.
 <
Zip
Keyword

49
<
Zip Ke y wor d

The zip() function takes multiple iterators as arguments and

returns an iterator of tuples with the first item in each of the
passed iterators as the first tuple. Second item in each of the
passed iterators as the second tuple and as on.

If the passed iterators have different lengths, the iterator with

the least items decides the length of the new iterator.

Syntax:

The zip function is useful in for loops where you want

corresponding elements of 2 or more [Link] makes the code
look much more readable and concise.
 <
Enumerate
function

51
<
E n u m erat e funct i on

The enumerate() method adds a counter to an iterable and

returns it as a list of tuples.

The enumerate function comes in handy when you want the

counter value along with the value itself while looping over the
iterable as well, thus making the code look much cleaner as
compared to adding an additional variable to keep a count
 <
Open
function

53
<
OPEN funct i on

The open() function is used to either read content from or write

content to a file based on the argument we pass. It is a common
file handling tool used in Python

Syntax:

Usage:

Parameters:
file - The path and name of the file
mode - A string, define which mode you want to open the file in:
"r" - Read - Default value. Opens a file for reading, error if
the file does not exist
"a" - Append - Opens a file for appending, creates the file
if it does not exist
"w" - Write - Opens a file for writing, creates the file if it
does not exist
"x" - Create - Creates the specified file, returns an error if
the file exist
 <
Recursion

55
<
Rec ursi on

Recursion can be remembered with the help of Matryoshka

dolls -- a set of wooden dolls of decreasing size placed one
inside another.

When you open a doll, you find another doll inside, and when you
open that one, there's another one inside. The act of doing this is
called recursion.

Recursion should always have a base case.

A recursive call must reach a base case to end the program.

Example:

Open a doll

If the doll is
If you find
empty,
another doll
You’re done
 <
Singly
linked
list

57
<
S i ng ly l in ke d li st

• A Linked List is a list that is linked to nodes.

• The first node is called the Head
• The last node is called Tail
• The Null signifies it’s the end of the list.
• The tail or last node points to Null.
• Each node points to the next node by means of a pointer.
It is a data structure consisting of a group of nodes that
together represent a sequence.

Example:

Head

Data Pointer Data Pointer Data Pointer Null

HEAD NULL
10 20 30
 <
Doubly
linked
list

59
<
D o ubly-li nke d list

A linked list in which each node has two pointers, p and n, such
that p points to the previous node and n points to the next node;
the last node's n pointer points to null.

10 20 30 40 Null

Circular-linked list: A linked list in which each node points to the

next node and the last node points back to the first node.

HEAD
66 77 55

TIME COMPLEXITY

Access Search Insert Remove

O(n) O(n) O(1) O(1)

 <
Stack

61
<
Stac k

• A Stack is a collection of elements, with two principle

operations: push, which adds to the collection, and pop, which
removes the most recently added element.
• You can think of stack as plates stacked on top of each
other vertically and you can only touch the top plate.
• Last in, first-out data structure (LIFO): the most recently added
object is the first to be removed

3 TOP

Basic operations of Stack

• push() — Inserts an element at the top
• pop() — Returns the top element after removing from the stack
• isEmpty() — Returns true if the stack is empty
• top() — Returns the top element without removing from the stack

TIME COMPLEXITY

Access Search Insert Remove

O(n) O(n) O(1) O(1)

 <
Queue

63
<
Q ue ue

• A Queue is a collection of elements, supporting two principle

operations: enqueue, which inserts an element into the queue,
and dequeue, which removes an element from the queue
• First in, first out data structure (FIFO): the oldest added object is
the first to be removed

Remove previous elements

1 FRONT

4 BACK

Insert new elements

Basic operations of Queue

• enqueue() — Inserts element to the end of the queue
• deque() — Removes an element from the start of the queue
• isEmpty() — Returns true if queue is empty
• top() — Returns the first element of the queue

TIME COMPLEXITY

Access Search Insert Remove

O(n) O(n) O(1) O(1)

 <
Tree

65
<
Tr e e

• Each node of the tree will have a root value and a list of
references to other nodes which are called child nodes
• Trees are not cyclic
Binary Tree
• A Binary Tree is a tree data structure in which each node can
have at most two children, which are referred to as the left child
and right child
• Full Tree: A tree in which every node has either 0 or 2 children
• Perfect Binary Tree: A binary tree in which all interior nodes
have two children and all leaf nodes are at the same level.
A perfect Binary Tree has everything filled in. All the leaf nodes
are full.
• Complete Tree: a binary tree in which every level except possibly
the last is full and all nodes in the last level are as far left as
possible

IMPORTANT TERMS IN TREES

• Path − Path refers to the sequence of nodes along the edges of

a tree.
• Root − The node at the top of the tree is called root. There is only
one root per tree and one path from the root node to any node.
• Parent − Any node except the root node has one edge upward to
a node called parent.
• Child − The node below a given node connected by its edge
downward is called its child node.
• Leaf − The nodes without child nodes.
• Subtree − Subtree is the descendants of a node.
• Traversing − Traversing means passing through nodes in an
order.
• Levels − Level of a node represents the generation of a node. If
the root node is at level 0, then its next child node is at level 1, its
grandchild is at level 2, and so on.
 <
Binary
Search
Tree

67
<
B i n ary Sea rch Tr e e

• All child nodes in the tree to the right node must be greater than
the current node.
• All child nodes in the tree to the left node must be lesser than
the current node.
• A binary search tree is a type of binary tree which maintains the
property that the value in each node must be greater than or
equal to any value stored in the left sub-tree, and less than or
equal to any value stored in the right subtree

10

6 12

3 8 15

4 9 13

BINARY SEARCH TREE TIME COMPLEXITY

Access Search Insert Remove

O(log(n)) O(log(n)) O(log(n)) O(log(n))

 <
Trie

69
<
Trie

• A Trie, sometimes called a radix or prefix tree is a specialized

Tree used in searching, most often in text.
• In most cases, it outperforms Binary Search Tree, Hash Tables
and most other Data Structures.
• Tries allows you to know if a word or a part of word exists in a
body of text.
• A Trie usually has an empty root node, which is the starting
point.
• All the descendants of a node have a common prefix, of the
String associated with that node,
• It can have multiple children
• Trie is used for searching words in a dictionary, providing auto
suggestion and IP routing.

START

A D N Z

S
R O E O E

E T W T N

Time complexity: O(length of the word)

Space Complexity: Because we use prefix such as N is used in
different word, we don’t have to store it multiple times. Because of
the prefixes you save a lot of space.
 <
heap

71
<
h eap

• Heap data structure is a complete binary tree that satisfies the

heap property.
• Max Heap: The key of each node is always greater than its child
nodes and the key of the root node is the largest among all
other nodes.
• Min Heap: The key of each node is always smaller than the child
nodes and the key of the root node is the smallest among all
other nodes.

HEAP DATA STRUCTURE

MAX HEAP
100

40 50

10 15 50 40

MIN HEAP
10

15 30

40 50 100 40
 <
Heapify

73
<<
To create a Heapify:
H eap i fy

Heapify is the process of creating a heap data structure from a

binary tree. It is used to create a Min-Heap or a Max-Heap.

• The index of left child is given by 2i + 1 and the right child is given
by 2i + 2.
• If leftChild is greater than currentElement set leftChildIndex as
largest.
• If rightChild is greater than element in largest, set
rightChildIndex as largest.
• Swap largest with currentElement
• Repeat the process until the subtrees are heapified.

Example:

TIME COMPLEXITY

Access Max/Min Insert Remove Max/Min

O(1) O(log(n)) O(log(n))

 <
Priority
Queue

75
<
P rio rity Que ue

• A type of data where each element has a priority.

• Elements with higher priority are served before elements with
lower priority.
• If elements with the same priority occur, they are served
according to their order in the queue.
• Basic operations of a priority queue are inserting, removing and
peeking elements.
• It is used for load balancing and interrupt handling in an
operating system.
• A comparative analysis of different implementations of priority
queue is given below.

Data Structure Peek Insert Delete

Linked List O(1) O(n) 1(n)

Binary Heap O(1) O(log n) O(log n)
Binary Search Tree O(1) O(log n) O(log n)
 <
Hashing

77
<
H ashi ng

• Hashing is the process of converting a given key into another

value.
• A hash function is used to generate the new value according to
a mathematical algorithm.
• A hash table stores key/value pairs in the form of a list where
any element can be accessed using its index.
• If two keys map to the same value, a collision occurs
• Hashing is also used in data encryption. Passwords can be
stored in the form of their hashes so that even if a database is
breached, plaintext passwords are not accessible.
• Some popular cryptographic hashes are MD5, SHA-1 and SHA-2

Collision Resolution
• Separate Chaining: In separate chaining, each bucket is
independent, and contains a list of entries for each index. The
time for hash map operations is the time to find the bucket
(constant time), plus the time to iterate through the list
• Open Addressing: In open addressing, when a new entry is
inserted, the buckets are examined, starting with the
hashed-to-slot and proceeding in some sequence, until an
unoccupied slot is found. The name open addressing refers to
the fact that the location of an item is not always determined
by its hash value
 <
Hash Map

79
<< H ash Ma p

A hash map is a data structure that can map keys to values. A

hash map uses a hash function to compute an index into an array
of buckets or slots, from which the desired value can be found.
• Key - a unique identifier used to associate each element (value)
in a map
• Value - elements associated by keys in a map

TIME COMPLEXITY

Insertion Deletion Search Space

Average case O(1) Average case O(1) Average case O(1)

Worst case O(n) Worst case O(n) Worst case O(n)
O(n)
 <
Selection
Sort

81
<
S e l ecti on Sort

The algorithm works by scanning a list of items for the smallest

element and then swapping that element for the first position.

Stable: No
Space Complexity: O(1)

TIME COMPLEXITY

Best Case Worst Case Average Case

O(n^2) O(n^2) O(n^2)

 <
Quick sort

83
<
Q uic k sort

Quick sort uses a pivoting technique to break the main list into
a smaller list and the smaller list uses the pivoting technique
unless they are sorted.

How Quicksort works?

• Quick sort follows the Divide and Conquer approach
• Choose a pivot
• Put all the numbers lesser than the pivot on the left side.
• The left and the right subparts are again partitioned by
selecting pivot elements for them.
• A pivot element is chosen from the array. You can choose any
element from the array as the pivot element.
• The elements smaller than the pivot element are put on the left
and the elements greater than the pivot element are put on the
right.
• It uses Recursion for implementation.

54 26 93 17 77 55 20

26 20 17 54 55 77 93

Stable: No
Space Complexity: O(log n)
TIME COMPLEXITY

Best Case Worst Case Average Case

O(nlog(n)) O(n^2) O(nlog(n))

 <
merge sort

85
<
merg e sort

• Merge sort is also a divide and conquers algorithm.

• It uses recursion to keep dividing an array into two halves.
• At the end, it merges the two sorted halves
• Any run of Merge sort can be visualized as a tree. The leaves of
the tree are the individual elements of the array. Each inner node
of the tree corresponds to merging two smaller arrays into one
larger array.

Divide phase
Divide the unsorted list into two sublists of about half the size.

Conquer phase
Sort each of the two sublists recursively until we have list sizes of
length 1, in which case the list items are returned.

Combine phase
Join the two sorted Sub lists back into one sorted list. When the
conquer step reaches the base step and we get two sorted
subarrays, we combine the results by creating a sorted array from
two sorted subarrays.

Stable: No
TIME COMPLEXITY

Best Case Worst Case Average Case

O(nlog(n)) O(nlog(n)) O(nlog(n))

 <
Breadth
First
Search

87
<
B r ea dt h F i rst Search

2 3

4 5 6 7

It explores all the nodes at the present depth before moving on

to the nodes at the next depth level.

Tree traversal path: [1,2,3,4,5,6,7]

Time Complexity:
Time complexity is 0(|V|), where |V| is the number of nodes.
We need to traverse all nodes.
Space complexity:
Space complexity is O(|V|) as well - since at worst case you need
to hold all vertices in the queue.
 <
Depth
First
Search

89
<
D e pt h F irst Search

2 5

3 4 6 7

It is an algorithm for traversing or searching tree or graph data

structures which uses the idea of backtracking. It explores all the
nodes by going forward if possible or uses [Link]
nodes are explored in depth.

Tree traversal path: [1,2,3,4,5,6,7]

Time Complexity:
Time complexity is O(|V|), where |V| is the number of nodes.
We need to traverse all nodes.
Space complexity:
A recursive implementation can have a O(h) space complexity
(worst case), where h is the maximal depth of your tree.

Using an iterative solution with stack is O(|V|)

 <
Graph

91
<
G rap h

• A graph data structure is a collection of nodes that have data

and are connected to other nodes.
• It consists of a collection of vertices V and a collection of edges
E, represented as ordered pairs of vertices (V,E)

Adjacency:
A vertex is said to be adjacent to another vertex if there is an
edge connecting them.

Path:
A sequence of edges that allows you to go from vertex A to
vertex B is called a path.

B
VERTEX EDGE

Undirected Graph:
A graph in which the adjacency relation is symmetric. So if there
exists an edge from node u to node v (u -> v), then it is also the
case that there exists an edge from node v to node u (v -> u)

Directed Graph:
A graph in which the adjacency relation is not symmetric. The
edges in such a graph are represented by arrows to show the
direction of the edge.
 <
B - Trees

93
<
B - Tr e e s

• B-tree nodes have more than two children.

• A B-tree node may contain more than just a single element.
• Rule 1: The root can have as few as one element (or even no
elements if it also has no children); every other node has at
least MINIMUM elements.
• Rule 2: The maximum number of elements in a node is twice the
value of MINIMUM.
• Rule 3: The elements of each B-tree node are stored in a partially
filled array, sorted from the smallest element (at index 0) to the
largest element (at the final used position of the array).
• Rule 4: The number of subtrees below a nonleaf node is always
one more than the number of elements in the node. Subtree 0,
subtree 1, ...
• Rule 5: For any nonleaf node:
· An element at index i is greater than all the elements in subtree
number i of the node, and
· An element at index i is less than all the elements in subtree
number i + 1 of the node.
• Rule 6: Every leaf in a B-tree has the same depth. Thus it ensures
that a B-tree avoids the problem of an unbalanced tree.

2 6

0 3 5 7
 <
B+ Trees

95
<
B+ T r e e s

B+ tree is an extension of B-tree and the data here is stored in leaf

nodes only. Due to this factor, searching in a B+ tree is faster and
efficient.
• Leaves are used to store data records.
• It stored in the internal nodes of the Tree.
• If a target key value is less than the internal node, then the point
just to its left side is followed.
• If a target key value is greater than or equal to the internal
node, then the point just to its right side is followed.
• The root has a minimum of two children.
• A comprehensive full scan of all the elements is a tree that
needs just one linear pass because all the leaf nodes of a B+
tree are linked with each other.

Search Operation
To find the required record, you need to execute the binary search
on the available records in the Tree. In case of an exact match
with the search key, the corresponding record is returned to the
user.
In case the exact key is not located by the search in the parent,
current, or leaf node, then a "not found message" is displayed to
the user.
The search process can be re-run for better and more accurate
results.

3 5

2 4 6

1 2 3 4 5 6 7
 <
ADVANCED
ALGORITHMS

97
<
Topo lo gi ca l Sort

• The topological sort algorithm takes a directed graph and

returns an array of the nodes where each node appears before
all the nodes it points to.
• Topological Sort is the linear ordering of a directed graph's
nodes such that for every edge from node u to node v, u comes
before v in the ordering.

Time Complexity: O(|V| + |E|)

D ij kstra's Algor i t hm
• Dijkstra's Algorithm is an algorithm for finding the shortest path
between nodes in a graph

Time Complexity: O(|V|^2)

Topo lo gi ca l Sort
• Bellman-Ford Algorithm is an algorithm that computes the
shortest paths from a single source node to all other nodes in a
weighted graph
• Although it is slower than Dijkstra's, it is more versatile, as it is
capable of handling graphs in which some of the edge weights
are negative numbers

Time Complexity:
Best Case: O(|E|)
Worst Case: O(|V||E|)
 <
Greedy
Algorithms

99
<
G r e edy A lgor it hms

• A greedy algorithm always takes the best/cheapest option

available at that moment, even if that might not be the best way
to go from an overall point of view.
• Problems must exhibit two properties in order to implement
a Greedy solution:
• Optimal Substructure
A problem has an optimal substructure if an optimal solution to
the entire problem contains the optimal solutions to the
sub-problems
• The Greedy Property
An optimal solution is reached by "greedily" choosing the locally
optimal choice without ever reconsidering previous choices.

GREEDY ALGORITH
LARGEST PATH 7
ACTUAL
LARGEST PATH

3 12

99 8 5 6

Prim's Algorithm
• Finds a minimum spanning tree for a weighted undirected graph.
Prim's find a subset of edges that forms a tree that includes
every node in the graph
• Time Complexity: O(|V|^2)
Kruskal's Algorithm
• Kruskal's Algorithm is also a greedy algorithm that finds a
minimum spanning tree in a graph. However, in Kruskal's, the
graph does not have to be connected
• Time Complexity: O(|E|log|V|)
 <
Runtime
Analysis

101
<
Ru ntime Analysi s

Data Structure Time Complexity

Average
Access Search Insertion Deletion

Array O(1) O(n) O(n) O(n)

Stack O(n) O(n) O(1) O(1)

Queue O(n) O(n) O(1) O(1)

Singly-Linked List O(n) O(n) O(1) O(1)

Doubly-Linked List O(n) O(n) O(1) O(1)

Skip List O(log(n)) O(log(n)) O(log(n)) O(log(n))

Hash Table N/A O(1) O(1) O(1)

Binary Search Tree O(log(n)) O(log(n)) O(log(n)) O(log(n))

 <
array
sorting
algorithms

103
<
a r ray s orti n g
a lgo r i thm s

Data Structure Time Complexity Space

Complexity
Best Average Worst Worst

Quicksort O(nlog(n)) O(nlog(n)) O(n^2) O(log(n))

Mergesort O(nlog(n)) O(nlog(n)) O(nlog(n)) O(n)

Timesort O(n) O(nlog(n)) O(nlog(n)) O(n)

Heapsort O(nlog(n)) O(nlog(n)) O(nlog(n)) O(1)

Bubblesort O(n) O(n^2) O(n^2) O(1)

Insertion sort O(n) O(n^2) O(n^2) O(1)

Selection sort O(n^2) O(n^2) O(n^2) O(1)

Tree sort O(nlog(n)) O(nlog(n)) O(n^2) O(n)

Shell sort O(nlog(n)) O(n(log(n))^2) O(n(log(n))^2) O(1)

Bucket sort O(n+k) O(n+k) O(n^2) O(n)

Radix sort O(nk) O(nk) O(nk) O(n+k)

Counting sort O(n+k) O(n+k) O(n+k) O(k)

Cubesort O(n) O(nlog(n)) O(nlog(n)) O(n)