Academic Session 2025-26

ODD Semester Jul-Dec 2025

UNIVERSITY INSTITUTE OF ENGINEERING
CSE-2nd year
CS201/IT201
SEMESTER 3
Advanced Data Structures and Algorithms
(24CSH-202)
Unit No. 2 Chapter No. 2.2 Topic : Non-linear Data Structures

____________________________________________________
Faculty Name and E_Code: Bhavneet Kaur(E14414)
Designation: Assistant Professor, Master Subject Co-ordinator
 Learning Objectives

•Understand the basic structure and properties of rooted trees,

binary trees, and binary search trees (BSTs).
•Analyze tree traversal techniques such as inorder, preorder,
postorder, and level-order.
•Differentiate between balanced and unbalanced trees; recognize
types like AVL trees.
•Explain the structure, properties, and operations of B-Trees.
•Implement heap data structures and perform heap sort
efficiently.
•Apply the concepts in solving real-world and competitive
programming problems.
 Non Linear Data Structure
• Data items are not arranged in a sequential manner.
• Elements are stored in a hierarchical or a network-based
structure that does not follow a sequential order.
• Allow efficient searching, insertion, and deletion of
elements from the structure.

Examples of Non Linear Data Structures:

Trees
Graphs, etc.
 Rooted trees

• A rooted tree is a tree with a special vertex

labelled as the ROOT of tree.
• Acts as point of reference for other vertices in
the tree.
• Usually kept at the top and list other vertices
below it.
• In the figure, the root vertex is shown with a
black border.
Tree comprises of:

Branch is just another name given to edges of the

tree.
Depth of a vertex is the number of branches in the
path from root to the vertex. So depth of the root
itself is zero.
Level of a vertex is number of vertex in the path from
root to the vertex. This is just one more than the
depth of the vertex. Level of root is 1.
Note: There can be multiple childs of a vertex, but
parent of a vertex is unique. Root is the only vertex in
a tree without any parent.
A leaf is a vertex without any child.
Height of tree is the maximum value of depth for any
vertex in the tree.
 Height of the Tree
A ROOT •Maximum depth = 3 (I, J, K are
at depth 3)
/ | \
No child •So, Height = 3
B C D Child Nodes
node
further /\ /\
E F G H
/ /\ Vertex Depth Level
I J K
A 0 1
B, C, D 1 2
Leaf Nodes (No Children) E, F, G, H 2 3
•C, E, G, I, J, K
I, J, K 3 4
 Binary Tree
• Hierarchal data structure in which each node has at most
two children.
• The child nodes are called the left child and the right
child.
• Linked list representation of a binary tree in which each
node has three fields:
• Pointer to store the address of the left child
• Data element
• Pointer to store the address of the right child
Tree Representation
 Properties
• A binary tree can have a maximum of nodes at level if the level of the root is
zero.
• When each node of a binary tree has one or two children, the number of leaf
nodes (nodes with no children) is one more than the number of nodes that
have two children.
• There exists a maximum of nodes in a binary tree if its height is , and the
height of a leaf node is one.
• If there are leaf nodes in a binary tree, then it has at least and at
most levels.
• A binary tree of nodes has minimum number of levels or minimum height.
• A binary tree of nodes has null references.
 Implementation of a
Binary Tree
We’ll use an auxiliary Node class that will store int values. And keep
a reference to each child:
class Node {
int value;
Node leftChild;
Node rightChild; Node(int value) {
this.value = value;
rightChild = null;
leftChild = null;
}}
 Types of Binary Trees
• Perfect Binary Tree
• Full Binary Tree
• A perfect binary tree is a special
• A binary tree is said to be a full type of binary tree in which all
binary tree when each internal the leaf nodes are at the same
node has zero or two children: level, and each internal node has
two children:
• Complete Binary Tree
• Degenerate or Pathological Tree
• A binary tree is referred to as a
A degenerate tree is a type of
complete binary tree when all of its
binary tree in which each internal
levels are completely filled. The
node has a single child, either the
only exception is possibly the
left child or the right child:
lowest level in which the nodes
must lean as left as possible:
• Skewed Binary Tree
• A binary tree is said to be a skewed binary tree if all of its internal
nodes have exactly one child, and either left children or right
children dominate the tree. In particular, there exist two types of
skewed binary trees: left-skewed binary tree and the right-skewed
binary tree:
• Balanced Binary Tree
• A balanced binary tree is also a special type of binary tree in
which the difference of height between the left and the right
subtrees for each node is at most one:
 Binary Search Tree
• Binary search tree, also known as an ordered or sorted binary tree,
is a rooted binary tree data structure in which each internal node
stores a key that is larger than all keys in the node’s left subtree
but less than those in the node’s right subtree.

Difference between a Binary tree and a Binary Search Tree?

• A Binary Tree is a simple structure with the simple constraint that
no parent can have more than two offspring, but a Binary Search
Tree is a version of the binary tree that follows a certain order in
which the nodes should be ordered.
 • Binary search trees. For any node x, the
keys in the left subtree of x are at most
x:key, and the keys in the right subtree of
x are at least x:key. Different binary
search trees can represent the same set
of values. The worst-case running time
for most search-tree operations is
proportional to the height of the tree.
(a) A binary search tree on 6 nodes with
height 2. The top figure shows how to
view the tree conceptually, and the
bottom figure shows the left, right, and p
attributes in each node
(b) A less efficient binary search tree, with
height 4, that contains the same keys.
It is called a binary tree because each tree node has a maximum of
two children.

It is called a search tree because it can be used to search for the

presence of a number in O(log(n)) time.

The properties that separate a binary search tree from a

regular binary tree is:
All nodes of left subtree are less than the root node
All nodes of right subtree are more than the root node

Both subtrees of each node are also BSTs i.e. they have the above
two properties.
• Wrong
representation as 2
should be in the left
subtree of root 3.

• Correct
representation of
BST.
 Tree Operations

Search Operation Insert Operation

• • Algorithm:
Algorithm:
If root == NULL return NULL; If If node == NULL return
number == root->data createNode(data) if (data <
return root->data; If node->data) node->left =
number < root->data insert(node->left, data); else
return search(root->left) If if (data > node->data) node-
number > root->data >right = insert(node->right,
return search(root->right) data); return node;
 Deletion Operation
• Case I • Case III
In the first case, the node to be deleted is In the third case, the node to be deleted has
the leaf node. In such a case, simply two children. In such a case follow the
delete the node from the tree. steps below:
• Case II Get the inorder successor of that node.
In the second case, the node to be Replace the node with the inorder successor.
deleted lies has a single child node. Remove the inorder successor from its
In such a case follow the steps original position.
below:
Replace that node with its child node.
Remove the child node from its original
position.
 Traversal of trees INORDER

• 1. Depth First Search Traversal

It is a traversal algorithm in which, starting from
POSTORDER PREORDER
the Root, it explores all nodes along each
branch as deeply as possible until we get to
a leaf node and then return to the “trunk”
of the tree (backtracking).

Stack is used to implement depth-first search traversal,

follows the “LIFO” (Last In First Out) or “FILO” (First In
Last Out)
 In-order Traversal

If a binary tree is traversed in-order,

the output will produce sorted key
values in an ascending order.
Step 1 − Recursively traverse left
subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right
subtree.
D→B→E→A→F→C→G
 Pre-order Traversal

In this traversal method, the root

node is visited first, then the left
subtree and finally the right
subtree.
Step 1 − Visit root node.
Step 2 − Recursively traverse left
subtree.
Step 3 − Recursively traverse right
subtree. A→B→D→E→C→F→G
 Post-order Traversal
• In this traversal method, the
root node is visited last,
hence the name. First we
traverse the left subtree, then
the right subtree and finally
the root node.
• Step 1 − Recursively traverse
left subtree.
• Step 2 − Recursively traverse D→E→B→F→G→C→A
right subtree. Step 3 − Visit
root node.
 2. Breadth First Search Traversal
(Level Order Traversal)

• It is a traversal algorithm in which, starting

from Root, it visits all nodes of the current
level from left to right before moving to the
next level in the tree.
• Queue is used to implement Breadth First
Search/ Level Order Traversal, follows First-In-
First-Out (FIFO) principle
• Level order traversal: A B C D E
 Add the root node to the queue.
 Iterate while the queue is not empty and
print the value of the first node in the
queue.
 Add the left child of a node to the queue
(if it exists).
 Add the right child of a node to the
queue (if it exists).
 Balanced search trees
• 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.
• balance = height(left subtree) – height(right subtree)
• Balanced Binary Search trees are performance-wise
good as they provide O(log n) time for search, insert
and delete.
A balanced binary tree is a binary tree that
follows the 3 conditions:

• The height of the left and right tree for any node does not
differ by more than 1.
• The left subtree of that node is also balanced.
• The right subtree of that node is also balanced.
• A single node is always balanced. It is also referred to as a
height-balanced binary tree.
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.

Advantages of Balanced Binary Tree:

Non Destructive updates are supported by a Balanced Binary
Tree with the same asymptotic effectiveness.
Range queries and iteration in the right sequence are made
feasible by the balanced binary tree.
Types of Balanced Search Tree

• BSTs that maintain height balance.

AVL trees
• For for each node, the difference in height of its two
subtrees is in the range -1 to 1

• Binary version of a 2-3-4 tree.

• Here the the nodes have a ‘color’ attribute: BLACK or RED.
Red-Black trees
The tree maintains a balance measure called
the BLACK height

• Self-adjusting type of BST with the additional property

that recently accessed elements are quick to be access
again.
Splay trees • The basic operations such as insertion, look-up and removal
takes place in O(log n) amortized time. Insert/find always
rotates node to the root.
 Balancing a tree
• The depth of a typical node in an AVL tree approaches the
optimal value possible which is log Consequently, all searching
operations in an AVL tree have logarithmic worst-case bounds.
An update (insert or remove) in an AVL tree could destroy the
balance. Therefore we go about rebalancing before before the
operation can be considered complete.
• After an insertion, only nodes that are on the path from the
insertion point to the root can have their balances altered. This
affects the way we carry out rebalancing.
 Restoring balance of the tree
• Here the element 35 is inserted.
Therefore the three nodes that
take part in the rotation are the
deepest unbalanced node (here
45), the ancestor of the inserted
node (40) and the inserted node
(35).
 BST Ordering Property after a Rotation
• A rotation does not affect the
ordering property of a BST
(binary search tree). This is
explained in Figure alongside.
• Let us assume a e α, b e β and c
eg. This implies that a ≤ A ≤ b ≤ B
≤ c according to the BST tree
property.
• It can be seen that even after
rotation the same property is Maintaining BST Ordering
maintained. We will explain the property
actual procedure of rotation in
the next section.
 Rotation and BST Property

• BST ordering
property requirement
means that on the
left hand side tree T1
< x < y, x< T2< y and x
< y < T3. Now we
carry out a right
rotation of x about y
as shown in the
figure along side.
This means that the following changes are made:
•y which was the parent with x as left child (x<y) before rotation
now becomes the right child of parent x retaining the x<y
property.
•T2 which was the right subtree of x (x<T2<y) before rotation now
becomes the left sub-tree of y still maintaining the same relation.
•Therefore after rotation the same property T1 < x < y, x < T2< y
and x < y < T3is maintained.
•Same is applicable for left rotation.
Different Cases of Rotations

Case1. left sub-

tree of left
child (Single
Right Rotation)
Case 4. left
Case 2. right
sub-tree of
sub-tree of
right
right
child (Double
child (Single
Right – Left
Left Rotation)
Rotation)
Case 3. right
sub-tree of left
child (Double
Left – Right
Rotation)
Single Right
Rotation
In this case the left sub-tree of the left child of X violates the property. In
this Figure (a) this means sub-tree A, the left sub-tree of the left child Y of
X violates the property. We need to carry out single right rotation of X
about Y where X now becomes the right child of Y, and the right sub-tree
of Y becomes the left sub-tree of X.
• Figure (b) shows the three steps namely

• the left child x of a node y becomes y’s parent.

• y becomes the right child of x.
• The right subtree T2 of x, if any, becomes the left child of y

• Here the notation ((T1+T2)+T3) indicates that the subtrees T1

and T2 are children of the same parent and that the combined
subtree of (T1+T2) and subtree T3 are children of the root.
Moreover the sub-trees change positions from ((T1+T2) + T3)
before the rotation to positions (T1+(T2+T3)) after the rotation
still maintaining the BST property.
• Figure (c) shows the steps more in detail.
• The node k2 is the node at which the imbalance occurs and the
balance factor is violated since the height of subtree c has height
difference of 2 with the subtree A.
• The left child of k2 is given by k1=k2.left.
• The new left sub-tree of k2 is now is k1’s right sub-tree (B) that is
k2.left=k1.right
• The new right sub-tree of k1 is k2 that is k1.right=k2
• Now we return the root of the new balanced tree that is k1.
 Single Left Rotation

In this case the right sub-tree of the right child of X violates the property.

The above figure shows sub-tree A, the right sub-tree of the right child Y of X
that violates the property.

We need to carry out single left rotation of Y about X where X now becomes the
left child of Y, and the left sub-tree of Y becomes the right sub-tree of X.
• The above figure shows the three steps namely
 The right child y of a node x becomes x’s parent.
 x becomes the left child of y.
The left child T2 of y, if any, becomes the right child of x
• Moreover the sub-trees change positions from (T1 + (T2 + T3)) before
the rotation to positions ((T1 + T2) + T3)after the rotation still
maintaining the BST property.
• The above figure shows the steps more in detail.
The node k1 is the node at which the imbalance occurs and the balance factor is violated
where the height of subtree c differs with the height of subtree A by more than one.
The right child of k2 is given by k2=k1.right.
The new right sub-tree of k1 is now is k2’s left sub-tree (B) that is k1.right=k2.left (B)
The new left sub-tree of k2 is k1 that is k2.left=k1
Now we return the root of the new balanced tree that is k2.
Double Rotations

The other two cases of rotation are cases of two

single rotations.
When a new item is added to the sub-tree for an
inside grandchild (left-right or right-left), the
imbalance is fixed with a double right or left
rotation.
 Left Right Double Rotation

• When we have the situation where we have a left inside

grandchild (left-right) case we have left right double rotation.
• A left-right double rotation is equivalent to a sequence of
two single rotations where the first rotation on the original
tree is a left rotation between X’s left-child and grandchild
and the second rotation on this new tree is a right rotation
between X and its new left child.
• In this case the right sub-tree of the left child of X
violates the property.
• First we need to rotate the tree LEFT about X’s left
child (Y) and grandchild (Z) as shown in the above
figure which is similar to single left rotation.
• Now we need to carry out the single right
rotation of z about x in the modified tree
that is we rotate the tree RIGHT about X and
its new left child (Z) ,which is clearly shown
in the above figure.
• The given figure shows the steps more in detail.
 The first pivot for the left rotation is the left child (v) of the deepest unbalanced node (x).
 We carry out Single Left Rotation of w about the first pivot v
 Moreover during this single left rotation the sub-trees change positions from ((T1 + ((T2+T3) + T4) before the first rotation to positions
(((T1 + T2)+T3) + T4) after the rotation still maintaining the BST property.
 The second pivot for the right rotation is the deepest unbalanced node itself x.
 We carry out Single Right Rotation of w about x
 Moreover during this single right rotation the sub-trees change positions from (((T1 + T2)+T3) + T4) before the first rotation to
positions ((T1 + T2)+ (T3+ T4)) after the rotation still maintaining the BST property.
 Right-Left Double Rotation

• When we have the situation where we have a right inside

grandchild (right-left) then we have right left double
rotation.
• A right-left double rotation is equivalent to a sequence of
two single rotations where the first rotation on the original
tree is a right rotation between X’s right-child and grandchild
and the second rotation on this new tree is a left rotation
between X and its new right child.
• The figure shows the details of case 4.
• The left sub-tree of the right child of X violates the property.
First we need to rotate the tree RIGHT about X’s right child (Y)
and grandchild (Z) as shown which is similar to single right
rotation.
• Now we need to carry out the single left rotation
of z about x in the modified tree that is we rotate
the tree LEFT about X and its new right child (Z) .
Figure shows the steps more in detail.
 The first pivot for the right rotation is right child (w) of the deepest unbalanced node (x)
 We carry out Single Right Rotation of v about the first pivot w
 Moreover during this single left rotation the sub-trees change positions from (T1 + ((T2+T3) + T4))
before the first rotation to positions (T1 + (T2 (T3 + T4)) after the rotation still maintaining the BST
property.
 The second pivot for the right rotation is the deepest unbalanced node itself x.
 We carry out Single Left Rotation of v about x
 Moreover during this single right rotation the sub-trees change positions from (T1 + (T2 (T3 + T4))
before the first rotation to positions ((T1 + T2) + (T3 + T4)) after the rotation still maintaining the
BST property.
 B-Tree
• Properties of B-Tree:
• All leaves are at the same level.
• B-Tree is defined by the term minimum
degree ‘t‘. The value of ‘t‘ depends upon
disk block size.
• Every node except the root must contain at
least t-1 keys. The root may contain a
minimum of 1 key.
• All nodes (including root) may contain at
most (2*t – 1) keys.
 B-Tree(Contd.)
Number of children of a node is equal to the number of keys in it plus 1.
All keys of a node are sorted in increasing order. The child between two
keys k1 and k2 contains all keys in the range from k1 and k2.
B-Tree grows and shrinks from the root which is unlike Binary Search
Tree. Binary Search Trees grow downward and also shrink from
downward.
Like other balanced Binary Search Trees, the time complexity to search,
insert, and delete is O(log n).
Insertion of a Node in B-Tree happens only at Leaf Node.
• Following is an example of a B-Tree of minimum order 5 .
 Heap

• Heap is a complete binary tree data structure with the property that the value of a
parent node is either greater than or equal to (max heap) or less than or equal to
(min-heap) the values of its children.
• Heaps are used for efficient algorithms in sorting, selection, and as a priority queue.
• Each node of the tree corresponds to an element of the array. The tree is completely
filled on all levels except possibly the lowest, which is filled from the left up to a point.
• An array A[1:n] that represents a heap is an object with an attribute A:heap-size,
which represents how many elements in the heap are stored within array A.
That is, although A[1:n] may contain numbers, only the elements in A[1:n,heap-size],
where 0<=A.heap-size <= n, are valid elements of the heap.
• If A:heap-size = 0, then the heap is empty. The root of the tree is A[1] and given the
index i of a node, there’s a simple way to compute the indices of its parent, left child,
and right child with the one-line procedures PARENT, LEFT, and RIGHT.
Heap representations

MAX HEAP • A[Parent(i)>=A[i

]]

MIN HEAP • A[Parent(i),=A[i

]]
 Maintaining the heap property
• The procedure MAX-HEAPIFY on the facing page maintains the
max-heap property.
• Its inputs are an array A with the heap-size attribute and an index
i into the array.
• MAX-HEAPIFY assumes that the binary trees rooted at LEFT.[i]
and RIGHT[i] are max-heaps, but that A[i] might be smaller than
its children, thus violating the max-heap property.
• MAX-HEAPIFY lets the value at A[i] lets the value float down in
the max-heap so that the subtree rooted at index i obeys the
maxheap property.
• The action of MAX-HEAPIFY.(A,2) where A:heap-size = 10. The node that potentially
violates the max-heap property is shown in blue.
• (a) The initial configuration, with A[2] at node i =2 violating the max-heap property since
it is not larger than both children.
• The max-heap property is restored for node 2 in (b) by exchanging A[2]with A[4], which
destroys the max-heap property for node 4.
• The recursive call MAX-HEAPIFY.(A,4) now has i =4.
• After A[4] and A[9] are swapped, as shown in (c), node 4 is fixed up, and the recursive
call MAX-HEAPIFY A[9] yields no further change to the data structure.
T (n)= O(lg n) (By case 2 of
master theorem)
 Heap Sort in Data Structure
• Heap sort is a comparison-based sorting algorithm that
sorts an array in ascending or descending order by
transforming it into a binary heap data structure.

• It uses the concepts of max-heap and min-heap, where in

max-heap, the largest element is the root node, and in min-
heap, the smallest element is the root node.

• The algorithm uses the binary heap structure to efficiently

sort the elements.
• The HEAPSORT procedure takes O(n lg n) time,
since the call to BUILD-MAXHEAP takes O(n) time
and each of the n-1 calls to MAX-HEAPIFY takes
O(lg n) time.
 Binary Search Tree Complexities

Time Complexity
Here, n is the number of
nodes in the tree.
Space Complexity
The space complexity for
all the operations is O(n)
 Quiz
1.The number of leaf nodes in a rooted tree of height h with
branching factor k is at most. 6. What is the time complexity of building a
GATE CS 2015 Set 1 heap from an array of n elements? GATE CS
2018 Set 2
2. A full binary tree with n internal nodes contains how many
total nodes? 7.Which of the following sorting algorithms
UGC NET 2020 Dec (Shift 2) does not use comparison for sorting? GATE
CS 2020 Set 1
3. A binary search tree is constructed by inserting the keys 10, 8. In a B-tree of order m, what is the
1, 3, 5, 9, 12 in that order. The preorder traversal of the tree is? maximum number of keys in a node? UGC
GATE CS 2021 Set 1 NET 2018 July

4. A binary search tree is constructed by inserting the keys 10,

1, 3, 5, 9, 12 in that order. The preorder traversal of the tree is?
GATE CS 2021 Set 1

5. After inserting elements into an AVL tree, what is the number

of rotations required? GATE CS 2017 Set 1
 Quiz
Sample NPTEL-style Question Options
A) Edges to rootB) Nodes to rootC) Edges from
In a rooted tree, the depth of a node is defined as:
root to nodeD) Nodes from root to node
A full binary tree with n internal nodes has how many total
A) nB) 2nC) 2n + 1D) n + 1
nodes?
Which of the following traversals gives sorted output in a
A) PreorderB) InorderC) PostorderD) Level-order
BST?
A) D, B, E, A, F, CB) D, E, B, A, F, CC) B, D, E, A, C,
Preorder: [A, B, D, E, C, F]. What is the Inorder traversal?
FD) D, B, E, A, C, F
What is the max allowed height difference between left
A) 1B) 2C) 3D) Any value
and right subtrees in an AVL tree?
In a B-tree of order m, what is the max number of keys in a
A) mB) m - 1C) 2mD) m + 1
node?
A) RootB) Leftmost leafC) Rightmost leafD)
In a max-heap, the smallest element is located at:
Unknown without traversal
What is the worst-case time complexity of Heap Sort? A) O(n)B) O(n log n)C) O(n²)D) O(log n)

What is the height of a complete binary tree with n nodes? A) log₂(n)B) nC) n log₂(n)D) log₂(n+1)-1
 References
• https://books.google.co.in/books?id=law2E-
LPScIC&printsec=frontcover&dq=Trees+
%E2%80%93+Introduction+to+rooted+trees,+Binary+trees,
+Binary+Search+Tree,+traversal+of+trees,+Balanced+search+trees,
+Introduction+B-
Tree,Heap+Sort+NPTEL&hl=en&newbks=1&newbks_redir=1&sa=X&v
ed=2ahUKEwiflrG4z8-NAxW01TgGHfQ7JdUQ6AF6BAgMEAM
Relevant learning resources

https://archive.nptel.ac.in/content/storage2/courses/downl
oads_new/106105164/noc20_cs10_assigment_7.pdf

https://www.youtube.com/watch?v=6ysjqCUv3K4
 12

Thank You