Data Structures and Algorithms

UNIT 4 – TREES

4.1 Trees and Binary Trees – Concept and Terminology

4.1.1 Tree – Concept

● A tree is a non-linear data structure consisting of nodes connected by edges.

● It represents a hierarchical relationship among elements.

● Properties:

○ A tree with nn nodes has exactly n−1n-1 edges.

○ One node is designated as the root.

○ Every child node has exactly one parent (except the root).

Example Tree (General):

A (Root)

/ | \

B C D

/\ |

E F G

4.1.2 Binary Tree – Concept

● A binary tree is a tree where each node has at most two children.

● Children are called:

○ Left child

○ Right child

● Special Binary Trees:

○ Full Binary Tree: Every node has 0 or 2 children.

S.Y. B. Tech IT Page No. 1 MMCOE, Pune

Data Structures and Algorithms

○ Complete Binary Tree: All levels are filled except possibly the last, filled from left
to right.

○ Perfect Binary Tree: All levels are completely filled.

Example Binary Tree:

10

/ \

5 20

/\ /

2 7 15

4.1.3 Terminology

1. Root In a tree data structure, the first node is called as Root Node. Every tree must have
root node. We can say that root node is the origin of tree data structure. In any tree, there
must be only one root node. We never have multiple root nodes in a tree. In above tree, A is
a Root node

2. Edge In a tree data structure, the connecting link between any two nodes is called as
EDGE. In a tree with 'N' number of nodes there will be a maximum of 'N-1' number of
edges.

3. Parent In a tree data structure, the node which is predecessor of any node is called as
PARENT NODE. In simple words, the node which has branch from it to any other node is

S.Y. B. Tech IT Page No. 2 MMCOE, Pune

Data Structures and Algorithms

called as parent node. Parent node can also be defined as "The node which has child /
children". e.g., Parent (A,B,C,D).

4. Child In a tree data structure, the node which is descendant of any node is called as
CHILD Node. In simple words, the node which has a link from its parent node is called as
child node. In a tree, any parent node can have any number of child nodes. In a tree, all the
nodes except root are child nodes. e.g., Children of D are (H, I,J).

5. Siblings In a tree data structure, nodes which belong to same Parent are called as
SIBLINGS. In simple words, the nodes with same parent are called as Sibling nodes. Ex:
Siblings (B,C, D)

6. Leaf In a tree data structure, the node which does not have a child (or) node with degree
zero is called as LEAF Node. In simple words, a leaf is a node with no child. UNIT- IV TREES
4 In a tree data structure, the leaf nodes are also called as External Nodes. External node is
also a node with no child. In a tree, leaf node is also called as 'Terminal' node. Ex:
(K,L,F,G,M,I,J)

7. Internal Nodes In a tree data structure, the node which has atleast one child is called as
INTERNAL Node. In simple words, an internal node is a node with atleast one child. In a
tree data structure, nodes other than leaf nodes are called as Internal Nodes. The root node
is also said to be Internal Node if the tree has more than one node. Internal nodes are also
called as 'Non-Terminal' nodes. Ex:B,C,D,E,H

8. Degree In a tree data structure, the total number of children of a node (or)number of
subtrees of a node is called as DEGREE of that Node. In simple words, the Degree of a node
is total number of children it has. The highest degree of a node among all the nodes in a
tree is called as 'Degree of Tree'

9. Level In a tree data structure, the root node is said to be at Level 0 and the children of
root node are at Level 1 and the children of the nodes which are at Level 1 will be at Level 2
and so on... In simple words, in a tree each step from top to bottom is called as a Level and
the Level count starts with '0' and incremented by one at each level (Step). Some authors
start root level with 1.

10. Height In a tree data structure, the total number of edges from leaf node to a particular
node in the longest path is called as HEIGHT of that Node. In a tree, height of the root node
is said to be height of the tree. In a tree, height of all leaf nodes is '0'.

11. Depth In a tree data structure, the total number of edges from root node to a particular
node is called as DEPTH of that Node. In a tree, the total number of edges from root node to
a leaf node in the longest path is said to be Depth of the tree. In simple words, the highest

S.Y. B. Tech IT Page No. 3 MMCOE, Pune

Data Structures and Algorithms

depth of any leaf node in a tree is said to be depth of that tree. In a tree, depth of the root
node is '0'.

12. Path In a tree data structure, the sequence of Nodes and Edges from one node to
another node is called as PATH between that two Nodes. Length of a Path is total number of
nodes in that path. In below example the path A - B - E - J has length 4. 13. Sub Tree In a
tree data structure, each child from a node forms a subtree recursively. Every child
node will form a subtree on its parent node.

4.2 Expression Tree

● Definition: A binary tree that represents an arithmetic expression.

● Properties:

○ Leaf nodes → operands (constants/variables).

○ Internal nodes → operators (+, −, ×, ÷).

Example Expression:
(a+b)∗(c−d)(a + b) * (c - d)

Expression Tree:

(*)

/ \

(+) (-)

/ \ / \

a bc d

● Traversals:

S.Y. B. Tech IT Page No. 4 MMCOE, Pune

Data Structures and Algorithms

○ In-order: a + b * c - d (gives infix expression).

○ Pre-order: * + a b - c d (gives prefix expression).

○ Post-order: a b + c d - * (gives postfix expression).

4.3 Binary Tree as an ADT

Binary Search Trees

Binary Search Tree Representation

Binary Search tree exhibits a special behavior. A node's left child must have value less than its
parent's value and node's right child must have value greater than it's parent value

We're going to implement tree using node object and connecting them through references.

Definition: A binary search tree (BST) is a binary tree. It may be empty. If it is not
empty,then all nodes follows the below mentioned properties −

• Every element has a unique key.

• The keys in a nonempty left subtree (right subtree) are smaller (larger) than the key
in the root of subtree.

• The keys in a nonempty right subtree larger than the key in the root of subtree.

• The left and right subtrees are also binary search trees. left sub-tree and right sub-
tree and can be defined as −

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

S.Y. B. Tech IT Page No. 5 MMCOE, Pune

Data Structures and Algorithms

Fig: Example Binary Search Trees

ADT for Dictionary:

BST Basic Operations

The basic operations that can be performed on binary search tree data structure, are
following −

• Search − search an element in a binary search tree.

• Insert − insert an element into a binary search tree / create a tree.

• Delete − Delete an element from a binary search tree.

• Height -- Height of a binary search tree.

Searching a Binary Search Tree

Let an element k is to search in binary search tree. Start search from root node of the
search tree. If root is NULL, search tree contains no nodes and search unsuccessful.
Otherwise, compare k with the key in the root. If k equals the root’s key, terminate
search, if k is less than key value, search

element k in left subtree otherwise search element k in right subtree. The function
search recursively searches the subtrees.

Algorithm:Recursive search of a Binary Search Tree

S.Y. B. Tech IT Page No. 6 MMCOE, Pune

Data Structures and Algorithms

tree_pointer search(tree_pointer root, int key)

/* return a pointer to the node that contains key. If

there is no such node, return NULL */

if (!root) return NULL;

if (key == root->data) return root; if (key < root->data)

return search(root->left_child, key); return search(root->right_child,key);

Algorithm: Iteraive search of a Binary Search Tree

tree_pointer search2(tree_pointer tree, int key)

while (tree) {

if (key == tree->data) return tree; if (key < tree->data)

tree = tree->left_child; else tree = tree->right_child;

return NULL;

Analysis of Recursive search and Iterative Search Algorithms:

If h is the height of the binary search tree, both algorithms perform search in O(h) time.
Recursive search requires additional stack space which is O(h).

Inserting into a Binary Search Tree

The very first insertion creates the tree. Afterwards, whenever an element is to be
inserted. First locate its proper location. Start search from root node then if data is
less than key value, search empty location in left sub tree and insert the data.
Otherwise search empty location in right sub tree and insert the data.

S.Y. B. Tech IT Page No. 7 MMCOE, Pune

Data Structures and Algorithms

In a binary search tree, the insertion operation is performed with O(log n) time
complexity. In binary search tree, new node is always inserted as a leaf node. The
insertion operation is performed as follows...

Step 1: Create a newNode with given value and set its left and right to NULL. Step 2:
Check whether tree is Empty.

Step 3: If the tree is Empty, then set set root to newNode.

Step 4: If the tree is Not Empty, then check whether value of newNode is smaller or
larger than the node (here it is root node).

Step 5: If newNode is smaller than or equal to the node, then move to its left child. If
newNode is larger than the node, then move to its right child.

Step 6: Repeat the above step until we reach a node (e.i., reach to NULL) where search
terminates.

Step 7: After reaching a last node, then insert the newNode as left child if newNode is
smaller or equal to that node else insert it as right child.

Algorithm

Create newnode If root is NULL

then create root node return

If root exists then

compare the data with [Link]

while until insertion position is located If data is greater than [Link]

goto right subtree else

goto left subtree endwhile

insert newnode end If

Implementation

S.Y. B. Tech IT Page No. 8 MMCOE, Pune

Data Structures and Algorithms

The implementation of insert function should look like this −

Deleting a node

Remove operation on binary search tree is more complicated, than insert and search.
Basically, in can be divided into two stages:

• search for a node to remove

• if the node is found, run remove algorithm.

Remove algorithm in detail

Now, let's see more detailed description of a remove algorithm. First stage is identical
to algorithm for lookup, except we should track the parent of the current node.
Second part is more tricky. There are three cases, which are described below.

1. Node to be removed has no children. --This case is quite simple. Algorithm sets
corresponding link of the parent to NULL and disposes the node.

Example. Remove -4 from a BST.

2. Node to be removed has one child. In this case, node is cut from the tree and
algorithm links single child (with it's subtree) directly to the parent of the removed
node.

S.Y. B. Tech IT Page No. 9 MMCOE, Pune

Data Structures and Algorithms

3. Node to be removed has two children. --This is the most complex case. The deleted
node can be replaced by either largest key in its left subtree or the smallest in its
right subtree. Preferably which node has one child.

Deletion Operation in BST

In a binary search tree, the deletion operation is performed with O(log n) time
complexity. Deleting a node from Binary search tree has following three cases...

Case 1: Deleting a Leaf node (A node with no children) Case 2: Deleting a node with one
child

Case 3: Deleting a node with two children Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST... Step 1: Find the node to be
deleted using search operation

Step 2: Delete the node using free function (If it is a leaf) and terminate the function.
Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST... Step 1: Find the
node to be deleted using search operation

Step 2: If it has only one child, then create a link between its parent and child nodes.
Step 3: Delete the node using free function and terminate the function.

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST... Step 1: Find
the node to be deleted using search operation

Step 2: If it has two children, then find the largest node in its left subtree (OR) the
smallest node in its right subtree.

S.Y. B. Tech IT Page No. 10 MMCOE, Pune

Data Structures and Algorithms

Step 3: Swap both deleting node and node which found in above step.

Step 4: Then, check whether deleting node came to case 1 or case 2 else goto steps 2
Step 5: If it comes to case 1, then delete using case 1 logic.

Step 6: If it comes to case 2, then delete using case 2 logic.

Step 7: Repeat the same process until node is deleted from the tree.

/* deletion in binary search tree */

void deletion(struct treeNode **node, struct treeNode **parent, int data) { struct
treeNode *tmpNode, *tmpParent;

if (*node == NULL) return;

if ((*node)->data == data) {

/* deleting the leaf node */

if (!(*node)->left && !(*node)->right) { if (parent) {

/* delete leaf node */

if ((*parent)->left == *node) (*parent)->left = NULL;

else

(*parent)->right = NULL;

free(*node);

} else {

/* delete root node with no children */ free(*node);

/* deleting node with one child */

} else if (!(*node)->right && (*node)->left) {

/* deleting node with left child alone */ tmpNode = *node;

(*parent)->right = (*node)->left; free(tmpNode);

*node = (*parent)->right;

} else if ((*node)->right && !(*node)->left) {

S.Y. B. Tech IT Page No. 11 MMCOE, Pune

Data Structures and Algorithms

/* deleting node with right child alone */ tmpNode = *node;

(*parent)->left = (*node)->right; free(tmpNode);

(*node) = (*parent)->left;

} else if (!(*node)->right->left) {

/*

* deleting a node whose right child

* is the smallest node in the right

* subtree for the node to be deleted.

*/

tmpNode = *node;

(*node)->right->left = (*node)->left;

(*parent)->left = (*node)->right; free(tmpNode);

*node = (*parent)->left;

} else {

/*

* Deleting a node with two children.

* First, find the smallest node in

* the right subtree. Replace the

* smallest node with the node to be

* deleted. Then, do proper connections

* for the children of replaced node.

*/

tmpNode = (*node)->right; while (tmpNode->left) {

tmpParent = tmpNode; tmpNode = tmpNode->left;

S.Y. B. Tech IT Page No. 12 MMCOE, Pune

Data Structures and Algorithms

tmpParent->left = tmpNode->right; tmpNode->left = (*node)->left; tmpNode->right

=(*node)->right; free(*node);

*node = tmpNode;

} else if (data < (*node)->data) {

/* traverse towards left subtree */ deletion(&(*node)->left, node, data);

} else if (data > (*node)->data) {

/* traversing towards right subtree */ deletion(&(*node)->right, node, data);

Height of a Binary Search Tree:

Height of a Binary Tree For a tree with just one node, the root node, the height is
defined to be 0, if there are 2 levels of nodes the height is 1 and so on. A null tree (no
nodes except the null node) is defined to have a height of –1.

The following height function in pseudocode is defined recursively

S.Y. B. Tech IT Page No. 13 MMCOE, Pune

Data Structures and Algorithms

Example

Construct a Binary Search Tree by inserting the following sequence of numbers...

10,12,5,4,20,8,7,15 and 13

Above elements are inserted into a Binary Search Tree as follows...

S.Y. B. Tech IT Page No. 14 MMCOE, Pune

Data Structures and Algorithms

Types of Trees and Heap Data Structure

1. Optimal Binary Search Tree (OBST)

● Definition:
An Optimal Binary Search Tree (OBST) is a binary search tree designed to minimize the
expected search cost based on the probabilities of searching for each element.

● Key Idea:

S.Y. B. Tech IT Page No. 15 MMCOE, Pune

Data Structures and Algorithms

○ Frequently accessed elements are placed closer to the root, while rarely accessed
elements are placed deeper.

○ Helps reduce average search time.

● Example:
Suppose elements A, B, C have search probabilities: P(A)=0.5, P(B)=0.3, P(C)=0.2.

○ Placing A as root → expected search cost minimized.

○ Tree structure:

●
○ Searching for A → 1 comparison, B → 2 comparisons, C → 3 comparisons.

● Applications:

○ Database indexing.

○ Compiler symbol tables.

○ Any application requiring frequent searches with known probabilities.

2. AVL Trees

● Definition:

○ An AVL Tree is a self-balancing binary search tree where the height difference
between left and right subtrees of any node is at most 1.

○ Named after Adelson-Velsky and Landis.

● Balance Factor (BF):

BF=Height(Left Subtree)−Height(Right Subtree)BF = Height(Left\ Subtree) - Height(Right\
Subtree)
○ Allowed values: -1, 0, +1

● Rotations to Maintain Balance:

S.Y. B. Tech IT Page No. 16 MMCOE, Pune

Data Structures and Algorithms

○ LL Rotation (Single Right Rotation) – Left-Left imbalance

○ RR Rotation (Single Left Rotation) – Right-Right imbalance

○ LR Rotation (Double Rotation: Left then Right) – Left-Right imbalance

○ RL Rotation (Double Rotation: Right then Left) – Right-Left imbalance

● Example:

30

20

10

● BF at 30 = 2 → imbalance → perform LL rotation → balanced tree:

20

/ \

10 30

● Advantages:

○ Guarantees O(log n) search, insertion, and deletion.

○ Suitable for real-time systems where performance is critical.

3. Threaded Binary Trees

● Problem in Standard Binary Trees:

1. Traversals require recursion or stack → extra memory or overhead.

● Solution – Threaded Binary Tree:

1. Replace NULL pointers in nodes with pointers to the inorder predecessor or

successor.

S.Y. B. Tech IT Page No. 17 MMCOE, Pune

Data Structures and Algorithms

2. Reduces need for stack/recursion.

● Types:

1. Inorder Threaded Tree – threads follow inorder traversal

2. Preorder Threaded Tree – threads follow preorder traversal

3. Postorder Threaded Tree – threads follow postorder traversal

3.1 Inorder Threaded Binary Tree Traversals

● Concept:

○ Each node has left and right pointers:

■ If left child is null → points to inorder predecessor

■ If right child is null → points to inorder successor

● Preorder Traversal (of Inorder Threaded Tree):

○ Visit root → traverse left subtree → traverse right subtree

○ Move to left child if exists, else follow thread to successor

● Inorder Traversal (of Inorder Threaded Tree):

○ Follow threads to move from smallest to largest node

○ Example for tree with nodes A, B, C:

Inorder: A → B → C

● Advantages:

○ Reduces memory usage (no stack required).

○ Traversal is faster and simpler for large trees.

4. Heap – Heap Data Structure

● Definition:

S.Y. B. Tech IT Page No. 18 MMCOE, Pune

Data Structures and Algorithms

○ A Heap is a complete binary tree that satisfies the heap property.

○ Complete binary tree → all levels completely filled except possibly the last, filled left
to right.

4.1 Types of Heap

1. Max Heap

○ Each parent node ≥ children

○ Root node contains maximum element

○ Example:

50

/ \

30 40

/\

10 20

2. Min Heap

○ Each parent node ≤ children

○ Root node contains minimum element

○ Example:

10

/ \

20 30

/\

40 50

4.2 Heap Operations

S.Y. B. Tech IT Page No. 19 MMCOE, Pune

Data Structures and Algorithms

1. Insertion:

○ Insert at last position → percolate up to maintain heap property

2. Deletion (Root Node):

○ Replace root with last node → percolate down to maintain heap property

Pseudocode (Insert in Max Heap):

Insert(heap, x):

heap[++size] = x

i = size

while i > 1 and heap[i] > heap[i/2]:

swap(heap[i], heap[i/2])

i = i/2

4.3 Heap Sort

● Concept:

○ Sorts an array using heap structure

○ Steps:

1. Build Max Heap

2. Swap root (max) with last element

3. Reduce heap size → percolate down

4. Repeat until heap size = 1

● Example (Max Heap Sort):

○ Array: [4, 10, 3, 5, 1]

○ Max Heap: [10, 5, 3, 4, 1]

○ Extract max (10) → swap with last → [1, 5, 3, 4, 10] → percolate down → [5, 4, 3, 1,
10]

○ Continue → sorted array: [1, 3, 4, 5, 10]

● Complexity:

S.Y. B. Tech IT Page No. 20 MMCOE, Pune

Data Structures and Algorithms

○ Time: O(nlog⁡n)O(n \log n)

○ Space: O(1)O(1) for array-based implementation

Question Bank

Question Marks BL Level CO Mapped

Define a graph. 2 BL-1 CO3

2 What is the difference between a 2 BL-2 CO3

directed and undirected graph?

3 State the difference between 2 BL-2 CO3

adjacency matrix and adjacency list.

4 Define the degree of a vertex. 2 BL-1 CO3

5 What is a spanning tree? 2 BL-1 CO3

6 What is a cycle in a graph? 2 BL-1 CO3

7 Mention any two applications of 2 BL-1 CO4

graphs.

8 Perform BFS traversal starting from 4 BL-3 CO4

vertex A for the given graph.

9 Perform DFS traversal starting from 4 BL-3 CO4

vertex A for the given graph.

10 Represent the following graph using 4 BL-3 CO3, CO4

adjacency matrix and adjacency list:
Vertices A,B,C,D; Edges: A-B, A-C, B-D,
C-D

11 Draw the MST using Prim’s algorithm 4 BL-3 CO4

for the given weighted graph.

12 Draw the MST using Kruskal’s 4 BL-3 CO4

algorithm for the given weighted
graph.

13 Apply Dijkstra’s algorithm to find 6 BL-3 CO4

shortest paths from vertex A in the
given weighted graph.

14 Compare Prim’s and Kruskal’s 6 BL-4 CO1, CO4

algorithm for finding MST in terms of
approach and complexity.

S.Y. B. Tech IT Page No. 21 MMCOE, Pune

Data Structures and Algorithms

15 Draw and explain the BFS and DFS 6 BL-4 CO1, CO4
tree starting from vertex A.

16 Construct an MST using Kruskal’s 6 BL-6 CO4

algorithm for the given weighted
graph and show all steps.

17 Evaluate the given graph 6 BL-5 CO1, CO3

representation and suggest whether
adjacency matrix or list is better and
why.

18 Given a DAG, perform topological sort 6 BL-3 CO4

using Kahn’s algorithm and explain
each step.

19 Analyze a weighted graph and explain 6 BL-4 CO1, CO4

which edges would be included in MST
using Prim’s algorithm.

20 Compare BFS and DFS with respect to 6 BL-5 CO1, CO2

time complexity and applications.

S.Y. B. Tech IT Page No. 22 MMCOE, Pune