MODULE-4[CHAPTER-1]

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT
BINARY SEARCH TREES:
 Definition:
 A binary search tree is a binary tree.
 It may be empty.
 If it is not empty, it satisfies the following properties:
 1. Every element has a key, and no two elements have
the same key, that is, the keys are unique.
 2. The keys in a non-empty left subtree must be smaller
than the key in the root of the subtree.
 3. The keys in a non-empty right subtree must be larger
than the key in the root of the subtree.
 4. The left and right subtrees are also binary search
trees.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 2
Searching A Binary Search Tree
 Suppose we wish to search for an element with a key.
 We begin at the root.
 If the root is NULL, the search tree contains no elements and
the search is unsuccessful.
 Otherwise, we compare key with the key value in root.
 If key equals root's key value, then the search terminates
successfully.
 If key is less than root's key value, then no element in the right
subtree can have a key value equal to key.
 Therefore, we search the left subtree of root.
 If key is larger than root's key value, we search the right
subtree of root.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 3
Recursive search of a binary search tree
tree_pointer search(tree_pointer root, int key)
{
if (root == NULL) // Tree empty or key not found
return NULL;
if (key == root->data) // Key found
return root;
if (key < root->data) // Search left subtree
return search(root->left_child, key);
return search(root->right_child, key); // Search right subtree
}

 We can easily replace the recursive search function with a comparable iterative one.
 The function searches! accomplishes this by replacing the recursion with a while loop.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 4
Iterative search of a binary search tree
tree_pointer search2(tree_pointer tree, int key)
{
// Search until tree becomes NULL
while (tree != NULL) {
if (key == tree->data) // Key found
return tree;
else if (key < tree->data) // Move to left subtree
tree = tree->left_child;
else // Move to right subtree
tree = tree->right_child;
}
// If loop ends, key is not found
return NULL;
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 5
Inserting into A Binary Search Tree:
 To insert a new element, key, we must first verify that the key is different from
those of existing elements.
 To do this we search the tree.
 If the search is unsuccessful, then we insert the element at the point the search
terminated.
 For instance, to insert an element with key 80 into the tree,
 we first search the tree for 80. This search terminates unsuccessfully, and the last
node examined has value 40. We insert the new element as the right child of this
node.
 The resulting search tree is shown in Figure 5.31(a). Figure 5.31(b) shows the
result of inserting the key 35 into the search tree of Figure 5.31(a).
 This strategy is implemented by insert-node (Program 5.17). This uses the function
modified -search which is a slightly modified version of function search 2 (Program
5.16). This function searches the binary search tree *node for the key num.
 If the tree is empty or if num is present, it returns NULL. Otherwise, it returns a
pointer to the last node of the tree that was encountered during the search. The
new element is to be inserted as a child of this node.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 6
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 7
PSEUDOCODE for insert_node()
Algorithm INSERT_NODE(root, num)
1. temp ← MODIFIED_SEARCH(root, num)
2. If temp is NULL AND root is NULL
// Tree is empty → create first node
Create new node ptr
Set [Link] = num
Set ptr.left_child = NULL
Set ptr.right_child = NULL
root ← ptr
return
3. If num already exists in the tree (temp = NULL)
Do nothing
return

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 8
4. // Insert as left or right child of temp
Create new node ptr
Set [Link] = num
Set ptr.left_child = NULL
Set ptr.right_child = NULL
5. If num < [Link]
temp.left_child ← ptr
Else
temp.right_child ← ptr

End INSERT_NODE

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 9
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *left_child;
struct node *right_child;
} *tree_pointer;
// Search the correct position & return pointer to parent
tree_pointer modified_search(tree_pointer root, int key) {
tree_pointer parent = NULL;
while (root != NULL) {
parent = root;
if (key == root->data)
return NULL; // key already exists
else if (key < root->data)
root = root->left_child;
else
root = root->right_child;
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 10
return parent; // parent node where new node will be attached
}
void insert_node(tree_pointer *node, int num) {
tree_pointer ptr, temp;
temp = modified_search(*node, num);
// If num does NOT exist OR tree is empty
if (temp != NULL || *node == NULL) {
ptr = (tree_pointer)malloc(sizeof(struct node));
if (ptr == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(1);
}
ptr->data = num;
ptr->left_child = ptr->right_child = NULL;
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 11
if (*node == NULL) {
// First node
*node = ptr;
}
else if (num < temp->data) {
temp->left_child = ptr;
}
else {
temp->right_child = ptr;
}
}}
// Utility - inorder traversal
void inorder(tree_pointer root) {
if (root) {
inorder(root->left_child);
printf("%d ", root->data);
inorder(root->right_child);
}
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 12
int main() {
tree_pointer root = NULL;

insert_node(&root, 50);
Inorder traversal: 20 30 40 50 60 70 80
insert_node(&root, 30);
insert_node(&root, 70);
insert_node(&root, 20);
insert_node(&root, 40);
insert_node(&root, 60);
insert_node(&root, 80);

printf("Inorder traversal: ");

inorder(root);

return 0;
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 13
Deletion from A Binary Search Tree:
 Deletion of a leaf node is easy.
 For example, to delete 35 from the tree ,we set the left child field of its
parent to NULL and free the node.
 This gives us the tree of The deletion of a non-leaf node that has only a
single child is also easy.
 We erase the node and then place the single child in the place of the erased
node. For example, if we delete 40 from the tree

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 14
 When we delete a non-leaf node with two children, we replace the node with
either the largest element in its left subtree or the smallest element in its
right subtree.
 Then we proceed by deleting this replacing element from the subtree from
which it was taken. For instance, suppose that we wish to delete 60 from the
tree.
 We may replace 60 with either the largest element (55) in its left subtree or
the smallest element (70) in its right subtree.
 Suppose we opt to replace it with the largest element in the left subtree. We
move the 55 into the root of the subtree.
 We then make the left child of the node that previously contained the 55 the
right child of the node containing 50, and we free the old node containing 55.
 One may verify that the largest and smallest elements in a subtree are always
in a node of degree zero or one.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 15
 When deleting a node with two children (like 60):
 We can replace it by either:
 Largest element in left subtree (Inorder Predecessor)
 Smallest element in right subtree (Inorder Successor)
 In this explanation, we choose largest element in left subtree, which is 55.
 After replacing:
 Move 55 into position of 60
 Fix links:
The node that contained 55 might have a left child only.
 Attach that left child to the right of 50

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 16
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 17
Pseudocode – Delete Using Inorder Predecessor (Largest in Left Subtree)

function deleteNode(root, key):

if root == NULL:
return NULL
if key < [Link]:
[Link] = deleteNode([Link], key)
else if key > [Link]:
[Link] = deleteNode([Link], key)
else:
// Node found
// Case 1: No child
if [Link] == NULL and [Link] == NULL:
free(root)
return NULL
// Case 2: One child
else if [Link] == NULL:
temp = [Link]
free(root)
return temp

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 18
 else if [Link] == NULL:
temp = [Link] 60
free(root) / \
40 80
return temp
/ \ /
// Case 3: Two children 30 50 70
else: \
// find inorder predecessor (largest in left subtree) 55
pred = [Link]
while [Link] != NULL:
pred = [Link] 55
/ \
// replace root value with predecessor value 40 80
/ \ /
[Link] = [Link]
30 50 70

// delete predecessor recursively

[Link] = deleteNode([Link], [Link])

return root
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 19
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int val) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->left = newNode->right = NULL;
return newNode;
}
struct Node* insert(struct Node* root, int val) {
if (root == NULL)
return createNode(val);

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 20
if (val < root->data)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
return root;
}
// Find largest in left subtree (inorder predecessor)
struct Node* findPredecessor(struct Node* root) {
root = root->left;
while (root->right != NULL)
root = root->right;
return root;
}
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL)
return NULL;

if (key < root->data)

root->left = deleteNode(root->left, key);

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 21
else if (key > root->data)

root->right = deleteNode(root->right, key);

else {

// Case 1: No child

if (root->left == NULL && root->right == NULL) {

free(root);

return NULL;

// Case 2: One child

else if (root->left == NULL) {

struct Node* temp = root->right;

free(root);

return temp;

else if (root->right == NULL) {

struct Node* temp = root->left;

free(root);

return temp;

}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 22
// Case 3: Two children
else {
struct Node* pred = findPredecessor(root);
// Replace value
root->data = pred->data;
// Delete predecessor
root->left = deleteNode(root->left, pred->data);
}
}
return root;
}
void inorder(struct Node* root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 23
int main() {
struct Node* root = NULL;
root = insert(root, 60);
root = insert(root, 40); Inorder before deletion: 30 40 50 55 60 70 80
root = insert(root, 80); Inorder after deletion: 30 40 50 55 70 80
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 55); // predecessor
root = insert(root, 70);
printf("Inorder before deletion: ");
inorder(root);
root = deleteNode(root, 60);
printf("\nInorder after deletion: ");
inorder(root);

return 0;
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 24
Joining and splitting Binary search tree:
 In a binary search tree, the following additional operations are useful in certain
applications.
 (a) three Way Join (small, mid, big): This creates a binary search tree consisting of
the pairs initially in the binary search trees small and big, as well as the pair mid.
 It is assumed that each key in small is smaller than mid, key and that each key in
big s greater than mid. key.
 Following the join, both small and big are empty.
 (b) two Way Join (small, big): This joins the two binary search trees small and big
to obtain a single binary search tree that contains all the pairs originally in smalt
and big.
 It is assumed that all keys of small are smaller than all keys of big and that
following the join both small and big are empty.
 (c) split (theTree ,k, small, mid, big): The binary search tree the Tree is split into
three parts: small is a binary search tree that contains all pairs of the Tree that
have key less than k; mid is the pair (if any) in the Tree whose key is k, and big is a
binary search tree that contains all pairs of the Tree that have key larger than k.
 Following the split operation theTree is empty. When the Tree has no pair whose
key is k, [Link] is set to -1 (this assumes that-1 is not a valid key for a dictionary
pair).

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 25
 1. Three-Way Join (small, mid, big)
 This operation creates one new BST by combining:
 small → all keys smaller than [Link]
 mid → a single node
 big → all keys greater than [Link]
 Assumptions
 Every element in small < [Link]
 Every element in big > [Link]
 After joining → small and big become EMPTY.

 How Three-Way Join Works

 Step 1
 Take the node mid as the root.
 Step 2
 Attach:
 small → as left subtree
 big → as right subtree

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 26
 mid
 / \
 small big
 Result: A perfectly valid BST
 Why?
Because all elements in small < mid < elements in big.

 2. Two-Way Join (small, big)

 We merge two BSTs:
 All elements of small < all elements of big
 After join → both become EMPTY.
 How Two-Way Join Works
 To join two trees, we must find a proper root.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 27
 METHOD
 Find the maximum node in small
 Remove it from small
 Make it the root
 Attach:
 the remaining small as left subtree
 big as right subtree
 Before Join:
 small: all small keys
 big: all big keys
 Find max(small) → M

 After Join:

 M
 / \
 small big

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 28
 Split(theTree, k, small, mid, big)
 Split divides one BST into three parts:
 small → keys < k
 mid → the node whose key = k (or [Link] = –1 if not found)
 big → keys > k
 after split → theTree becomes EMPTY


 How Split Works

 We recursively search for key k.
 CASE 1 — Key found
 Suppose theTree contains key k at node N.
 N (key = k)
 / \
 (small part) (big part)
 So:
 small = subtree on the left
 mid = N
 big = subtree on the right

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 29
 CASE 2 — Key < current node
 We go LEFT.
 root
 / \
 Tleft Tright
 If k < [Link]:
 Split [Link] based on k
 root and [Link] become part of big
 Eventually:
 small → from left split
 mid → from left split
 big → combine(root, right subtree)

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 30
 CASE 3 — Key > current node
 We go RIGHT.
 If k > [Link]:
 Split [Link]
 root and [Link] become part of small
 Eventually:
 small → combine(root, left subtree)
 mid → from right split
 big → from right split

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 31
 Operation Input Trees Output Trees Purpose
Three-way join Combine left,
small + mid +
(small, mid, one BST root, right → one
big
big) BST
Merge two BSTs
Two-way join
small + big one BST when all small <
(small, big)
all big
Split(theTree, Divide BST into
one BST small, mid, big
k) < k, = k, > k

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 32
[Link]: Three-Way Join (small, mid, big)

function threeWayJoin(small, mid, big):

[Link] = small
[Link] = big

small = NULL
mid
big = NULL
/ \
small big
return mid

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 33
2. Pseudocode: Two-Way Join (small, big)
function twoWayJoin(small, big):
if small == NULL:
result = big
big = NULL
return result
// Find max element in small
parent = NULL
curr = small
while [Link] != NULL:
parent = curr
curr = [Link]

// curr is maximum
maxNode = curr

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 34
// Remove maxNode from small
if parent != NULL:
[Link] = [Link]
else:
small = [Link]
// Attach
[Link] = small
[Link] = big

small = NULL
big = NULL

return maxNode

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 35
3. Pseudocode: Split(tree, k, small, mid, big)
function split(tree, k, small, mid, big):
if tree == NULL:
small = NULL
[Link] = -1
[Link] = NULL
big = NULL
return
if k == [Link]:
mid = tree
small = [Link]
big = [Link]
tree = NULL
return
if k < [Link]:
// split left subtree
split([Link], k, small, mid, tempRight)
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 36
// tree becomes part of big
[Link] = tempRight
big = tree
tree = NULL
else:
// split right subtree
split([Link], k, tempLeft, mid, big)

// tree becomes part of small

[Link] = tempLeft
small = tree
tree = NULL

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 37
 SPLIT(tree, k)
 Example:
 50
 / \
 20 70
 / \
 60 80
 split(tree, 70)
 small = {50,20,60}
 mid = 70
 big = {80}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 38
 TWO-WAY JOIN(small, big)
 small: {20,50,60}
big: {80}
 Find largest of small = 60 → becomes root.
 60
 / \
 small big


 THREE-WAY JOIN(small, mid, big)

 mid
 / \
 small big

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 39
Height of a binary search tree:

 Unless care is taken, the height of a binary search tree with n elements can
become as large as n. This is the case, for instance, when we use insert-node
to insert the keys 1, 2, 3, • • •, n, in that order, into an initially empty binary
search tree.
 However, when insertion and deletions are made at random using the above
functions, the height of the binary search tree is O(log2n), on the average.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 40
1. When Height Becomes as Large as n (Worst Case)

 This happens when the keys are inserted in sorted order (either increasing or
decreasing). 1
 Example \
2
 Insert the following keys into an empty BST: \
 1, 2, 3, 4, 5, 6, 7, ..., n 3
\
 Resulting BST (Skewed Tree)
4
\
5
\
.
.
 This is called a right-skewed tree. \
n
 Height = n
 Because every node has only one child, and it forms a linked list.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 41
2. When Insertions and Deletions Are Random (Average Case)

 If we insert elements in random order, not sorted order, the tree tends to
stay balanced by probability, not by design.
 Example
 Insert random keys into an empty BST:
 50, 20, 70, 10, 30, 60, 80
 Resulting BST looks roughly balanced:
 50
 / \
 20 70
 / \ / \
 10 30 60 80

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 42
 Height ≈ O(log₂ n)
 For n = 7 elements:
 log₂ 7 ≈ 2.8
 Height here = 2 (root = level 0)
 This is close to the expected height of a balanced tree.


 Why Is the Average Height O(log n)?

 Because:
 There are many possible insertion orders.
 Most orders produce relatively balanced trees.
 Only a small fraction of insertion orders produce the worst case (sorted
inserts).
 So random insertions → balanced BST on average.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 43
Pseudocode (Worst + Average)
Algorithm DemonstrateBSTHeights(n):
// Worst Case
tree1 ← EMPTY
for key = 1 to n do
INSERT(tree1, key)
print("Height of worst-case tree =", HEIGHT(tree1))

// Average Case (Random keys)

tree2 ← EMPTY
for i = 1 to n do
key ← RANDOM_VALUE()
INSERT(tree2, key)
print("Height of average-case tree =", HEIGHT(tree2))

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 44
SELECTION TREE:
Introduction:
 Suppose we have k ordered, called and is in merged into single ordered
sequence.
 Each run consists of some records and is in non-decreasing order of a
designated field called the key.
 Let n be the number of records in all k runs together task can be by the
record with the smallest key.
 The smallest has to be found from k possibilities, and it could be the leading
record in any of the k runs.
 The most direct way to merge k runs is to make k-1 to determine the next
record to output.
 For k > 2, we can achieve a reduction in the number of needed to find the
next smallest element by using the selection tree data structure.
 There are two kinds of selection trees: winner trees and loser trees.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 45
Winner Tree:
 A winner tree is a binary tree in which each node represents the smaller of its two
children.
 Thus, the root node the smallest node in the tree. Figure 5.32 illustrates a winner
tree for the case k = 8.
 The of this winner tree may be compared to the playing of a tournament in which
the winner is the record with the smaller key.
 Then, each non-leaf node in the tree the winner of a , and the root node the
overall winner, or the smallest key.
 Each leaf node the first record in the corresponding run. Since the records being
merged are large, each node will contain only a pointer to the record it
represents.
 Thus, the root node contains a pointer to the first record in run 4 A winner tree
may be represented using the sequential allocation scheme for binary trees that
results from Lemma 5.4.
 The number above each node in Figure 5.32 is the address of the node in this
sequential. The record pointed to by the root has the smallest key and so may be
output.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 46
 Now, the next record from run 4 enters the winner tree. It
has a key value of 15.
 To the tree, the tournament has to be replayed only along
the path from node 11 to the root.
 Thus, the winner from nodes 10 and 11 is again node 11
(15 < 9) The new tree is shown in Figure 5.33.
 The is played between sibling nodes and the result put in
the parent node.
 Lemma 5.4 may be used to compute the address of sibling
and parent nodes efficiently.
 Each new take place at the next higher level in the tree.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 47
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 48
Loser Tree:
 After the record with the smallest key value is output, the winner tree of
Figure 5.32 is to be restructured.
 Since the record with the smallest key value is in run 4this re- involves
inserting the next record from this run into the tree.
 The next record has key value 15. are played between sibling nodes along the
path from node 11 to the root.
 Since these sibling nodes represent the losers of played earlier, we can
simplify the process by placing in each nonleaf node a pointer to the record
that loses the rather than to the winner of the tournament.
 A selection tree in which each nonleaf node retains a pointer to the loser is
called a loser tree. Figure 5.34 shows the
 loser tree that to the winner tree of Figure 5.32. For, each node the key value
of a record rather

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 49
 than a pointer to the record represented. The leaf nodes the first record in
each run.
 An additional node, node 0has been added to represent the overall winner of
the tournament.
 Following the output of the overall winner, the tree is by playing along the
path from node 11 to node 1The records with which these tournaments are to
be played are readily available from the parent nodes.
 As a result, sibling nodes along the path from 11 to 1 are not accessed.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 50
1. SELECTION TREE
 A selection tree is a complete binary tree used to repeatedly select the
smallest (or largest) element from a list.
 Purpose:
 Used in external sorting
 Used in tournament-style selection (like knockout matches)
 How it works:
 Each leaf node contains an input value.
 Each internal node stores the winner (minimum or maximum) of its two
children.
 The root contains the final winner (e.g., minimum element).
 Example
 Suppose we have values:
8 3 5 2

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 51
Build the tree:
2 ← smallest overall
/\
3 2
/\/\
8 35 2

 Compare 8 vs 3 → winner = 3
 Compare 8 vs 3 → winner = 3
 Compare 5 vs 2 → winner = 2
 Compare 3 vs 2 → winner = 2 at root
 This is a selection tree

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 52
PROGRAM — SELECTION TREE
#include <stdio.h>
#define MAX 8
int tree[2 * MAX];
int n;
// Build Selection Tree
void buildSelectionTree(int A[]) {
// copy leaves
for (int i = 0; i < n; i++)
tree[n + i] = A[i];
// build internal nodes
for (int i = n - 1; i > 0; i--) {
int left = tree[2 * i];
int right = tree[2 * i + 1];
tree[i] = (left < right) ? left : right; // winner
}
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 53
int main() {
int A[] = {7, 3, 9, 2};
n = 4;

buildSelectionTree(A);

printf("Smallest element (winner) = %d\n", tree[1]);

return 0;
}
Smallest element (winner) = 2

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 54
2. WINNER TREE
 A winner tree is a type of selection tree where:
 Each internal node stores the winner of the match between its two children.
 The root stores the overall winner.
 Used in k-way merging
Height = O(log n) → very efficient
 Diagram
 For the input:
 8 3 5 2
 Winner tree:
[2] ← overall winner
/ \
[3] [2]
/\ /\
[8] [3] [5] [2]
 Why "winner"?
 Because only the better element (min or max) moves upward.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 55
Program: Winner Tree
#include <stdio.h>
#define MAX 8 // maximum number of elements
int winnerTree[2 * MAX]; // tree array
int n;
// Function to build the winner tree
void buildWinnerTree(int A[]) {
// Copy leaves (input values)
for (int i = 0; i < n; i++)
winnerTree[n + i] = A[i];
// Build internal nodes
for (int i = n - 1; i > 0; i--) {
int left = winnerTree[2 * i];
int right = winnerTree[2 * i + 1];
// smaller value wins
winnerTree[i] = (left < right) ? left : right;
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 56
}
// Function to display the tree array
void printTree() {
printf("Winner Tree Array: \n");
for (int i = 1; i < 2 * n; i++) Smallest element (winner) = 2
printf("%d ", winnerTree[i]); Winner Tree Array: 2 3 2 8 3 5 2
printf("\n");
}
int main() {
int A[] = {8, 3, 5, 2};
n = 4;
buildWinnerTree(A);
printf("Smallest element (winner) = %d\n", winnerTree[1]);
printTree();
return 0;
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 57
3. LOSER TREE
 A loser tree is similar to a winner tree, BUT:
 Each internal node stores the loser of the match instead of the winner.
 The root stores the overall winner, but losers stored inside help faster updates.
 Why loser tree?
 Loser trees allow faster replacement when an element changes (important in external merge sort).
Example
 For the same input:
 8 3 5 2
 Loser tree structure:
[2] ← winner at root
/ \
3 5 ← losers
/\ /\
- 8 3 2 (losers on the path)
 Interpretation:
 When 3 vs 8 → 3 wins, 8 stored as loser
 When 5 vs 2 → 2 wins, 5 stored as loser
 At root: 3 vs 2 → 2 wins, 3 stored as loser
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 58
 So internal nodes store losers, while the root stores the winner.
 Difference Between Winner Tree and Loser Tree

Feature Winner Tree Loser Tree

Stores in internal nodes Winner of each match Loser of each match
Root contains Overall winner Overall winner
Update time after a
O(log n) but slower O(log n) and FASTER
change
Practical efficiency (used
Why used? Conceptual simplicity
in external sorting)
What rises upward? Winner Winner
Loser (winner hidden until
What is stored? Winner
root)
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 59
 In a Winner Tree, when a leaf changes
 You must replay matches all the way up, and update winners AND maybe
restructure.
 In a Loser Tree,
 You only update the path of losers, not the entire structure.
 Loser Tree keeps track of the second best competitor at each level.
So when the winner changes, it is very easy to find:
 Who it should compete with next
 What changes need to be made
 This makes Loser Tree excellent for k-way merging (used in merge sort,
external sorting, tournament selection).

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 60
 Winner Tree (stores winners):
 2
 /\
 3 2
 /\/\
 835 2
 Internal nodes store: 3, 2, and root 2


 Loser Tree (stores losers):

 2
 /\
 3 5
 /\/\
 - 83 2
 Internal nodes store: 8, 5, 3, and root winner 2
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 61
PROGRAM — LOSER TREE
#include <stdio.h>
#define MAX 8
#define INF 99999
int loser[MAX]; // loser at each node
int leaf[MAX]; // input values
int n;
// Match two players
int play(int i, int j) {
if (leaf[i] < leaf[j]) {
loser[j] = i; // j loses
return i; // i wins
} else {
loser[i] = j; // i loses
return j; // j wins
}
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 62
// Build the loser tree
int buildLoserTree() {
for (int i = 0; i < n; i++)
loser[i] = -1; // initialize
int winner = 0; // start with first leaf
for (int i = 1; i < n; i++)
winner = play(i, winner);
return winner;
}
int main() { Smallest element (winner) = 2
int A[] = {7, 3, 9, 2}; Loser Tree: 1 3 1 -1
n = 4;
for (int i = 0; i < n; i++)
leaf[i] = A[i];
int w = buildLoserTree();
printf("Smallest element (winner) = %d\n", leaf[w]);
printf("Loser Tree: \n");
for (int i = 0; i < n; i++)
printf("%d ", loser[i]);
return 0;
}PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 63
Forest
 Definition: A forest is a set of n> 0 disjoint trees. When we remove the root of a
tree we obtain a forest. For example, removing the root of any binary tree
produces a forest of two trees.

 Three-tree forest
 Transforming a forest into a binary tree Definition:
 If T1, . . ., Tn is a forest of trees, then the binary tree corresponding to this
forest, denoted by B (T1, . . . , Tn),
 (1) is empty, if n = 0
 (2) has root equal to root (T1); has left subtree equal to B(T11,T12. . . T1m),
where T11, . . . ,T1m are the subtrees of root (T1); and has right subtree B(T2, . .
. ,Tn )

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 64
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 65
Forest Traversal
 Preorder Traversal:
 Binary tree representation of forest
 The preorder traversal of T is equivalent to visiting the nodes of Fin tree
preorder. We define this as:
 1. If F is empty, then return.
 2. Visit the root of the first tree of F.
 3. Traverse the subtrees of the first tree in tree preorder.
 4. Traverse the remaining trees of F in preorder.
 Inorder Traversal:
 Inorder traversal of T is equivalent to visiting the nodes of F in tree inorder,
which is defined as:
 1. If F is empty, then return.
 2. Traverse the subtrees of the first tree in tree inorder.
 3. Visit the root of the first tree.
 4. Traverse the remaining trees in tree inorder.
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 66
 Postorder Traversal:
 There is no natural analog for the postorder traversal of the corresponding
binary tree of a forest.
 Nevertheless, we can define the postorder traversal of a forest, F, as:
 1. If F is empty, then return.
 2. Traverse the subtrees of the first tree of F in tree postorder.
 3. Traverse the remaining trees of F in tree postorder.
 4. Visit the root of the first tree of F.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 67
1. Preorder Traversal of a Forest
 For a forest F = T₁, T₂, T₃…
 Preorder(F) = Preorder(T1) → Preorder(T2) → Preorder(T3) → ...
 Preorder of a single tree:
 Visit Root → Left Subtree → Right Subtree
 Example Forest
 Tree 1: Tree 2:
 A D
 /\ /\
 B C E F
 Preorder Traversal:
 Tree1 preorder = A B C
 Tree2 preorder = D E F
 Final Preorder of the Forest
 ABCDEF

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 68
Preorder Traversal of a Forest
procedure PREORDER_FOREST(Forest F)
for each Tree T in F do
PREORDER_TREE(T)
end for
end procedure
procedure PREORDER_TREE(Node root)
if root == NULL then
return
end if
visit(root)
for each child C of root (from left to right) do
PREORDER_TREE(C)
end for
end procedure

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 69
Inorder Traversal of a Forest
 Inorder(F) = Inorder(T1) → Inorder(T2) → Inorder(T3) → ...
 Inorder of a single binary tree:
 Left Subtree → Root → Right Subtree
 Example Forest
 Tree 1: Tree 2:
 A D
 /\ /\
 B C E F
 Inorder Traversal
 Tree 1 Inorder
 Left → Root → Right:
 BAC
 Tree 2 Inorder
 Left → Root → Right:
 EDF
 Final Inorder Traversal of the Forest
 Combine both results:
 BACEDF
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 70
Inorder Traversal of a Forest
procedure INORDER_FOREST(Forest F)
for each Tree T in F do
INORDER_TREE(T)
end for
end procedure
procedure INORDER_TREE(Node root)
if root == NULL then
return
end if
INORDER_TREE([Link])
visit(root)
INORDER_TREE([Link])
end procedure
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 71
Postorder Traversal of a Forest
 For forest F = T₁, T₂, T₃…
 Postorder(F) = Postorder(T1) → Postorder(T2) → Postorder(T3) → ...
 Postorder of a tree:
 Left subtree → Right subtree → Root
 Example Same Forest
 Tree 1: Tree 2:
 A D
 /\ /\
 B C E F
 Postorder:
 Tree1 postorder = B C A
 Tree2 postorder = E F D
 Final Postorder of the Forest
 BCAEFD

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 72
Postorder Traversal of a Forest
procedure POSTORDER_FOREST(Forest F)
for each Tree T in F do
POSTORDER_TREE(T)
end for
end procedure
procedure POSTORDER_TREE(Node root)
if root == NULL then
return
end if
for each child C of root (from left to right) do
POSTORDER_TREE(C)
end for
visit(root)
end procedure

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 73
Representation of Disjoint Sets
Introduction
 The use of trees in the representation of sets.
 assume that the elements of the sets are the numbers 0, 1, 2,. . .n-1.
 In practice, these numbers might be indices into a symbol table that stores the
actual names of the elements.
 For example, if we have 10 elements numbered 0 through 9, we may partition
them into three disjoint sets, S1 = {0, 6, 7, 8), S2 = {1, 4, 9}, and S3 = {2, 3, 5}.
 Figure shows one possible representation for these sets.

 The minimal operations that we wish to perform on these sets are:

 Disjoint set union and Find(i).
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 74
 Example
 Suppose we have 10 elements:
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
 They are partitioned into three disjoint sets:
 S₁ = {0, 6, 7, 8}
 S₂ = {1, 4, 9}
 S₃ = {2, 3, 5}
 One possible tree representation is:
 Set S₁
 0
 /|\
 678

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 75
 Set S₂
 1
 /\
 4 9
 Set S₃
 2
 /\
 3 5
 Here, 0, 1, and 2 are the roots/representatives.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 76
Operations
MakeSet(n)
Initialize each element as its own parent.
MakeSet(n):
for i = 0 to n-1:
parent[i] = I

Find(i)
Return representative (root) of the set that contains i.
Find(i):
while (parent[i] != i):
i = parent[i]
return i

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 77
Union(x, y)
Join two sets.
Union(x, y):
rootX = Find(x)
rootY = Find(y)

if (rootX != rootY):
parent[rootY] = rootX

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 78
Program — Tree Representation of Disjoint Sets
#include <stdio.h>
int parent[100]; // parent array for disjoint sets
// Initialize each element as its own set
void makeSet(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// Find the representative (root) of a set
int Find(int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 79
// Union operation: join two sets
void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
parent[rootY] = rootX; // attach Y's tree under X
}}
// Display parent array
void display(int n) {
printf("\nElement : Parent\n");
for (int i = 0; i < n; i++) {
printf("%d %d\n", i, parent[i]);
}}
int main() {
int n = 10; // 10 elements: 0 to 9
makeSet(n);

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 80
// Creating sets as per your example:
// S1 = {0, 6, 7, 8}
Union(0, 6);
Union(0, 7);
Union(0, 8);
// S2 = {1, 4, 9}
Union(1, 4);
Union(1, 9);
// S3 = {2, 3, 5}
Union(2, 3);
Union(2, 5);
// Display final parents (tree representation)
display(n);

return 0;
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 81
 Definition: Weighting rule for union(i, j).
 If the number of nodes in tree i is less than the number in tree j then make j
the parent of i; otherwise make i the parent of j.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 82
void weighted_union(int i, int j)
{
int ri = find(i);
int rj = find(j);
if (ri == rj) return;
if (parent[ri] < parent[rj]) {
// ri has more nodes (more negative)
parent[ri] += parent[rj]; // update size
parent[rj] = ri; // attach j under i
}
else {
parent[rj] += parent[ri]; // update size
parent[ri] = rj; // attach i under j
}
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 83
C Code (Weighted Union + Find)
#include <stdio.h>
int parent[100];
// initial attempt at find()
int find1(int i)
{
for ( ; parent[i] >= 0; i = parent[i]);
return i;
}
// initial attempt at union()
void union1(int i, int j)
{
parent[i] = j;
}

int main()
{

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 84
// Initialize parent array to -1 (each element is a root)
for (int k = 0; k < 10; k++)
parent[k] = -1;

// Example use:
Find(3) = 0
union1(3, 1); // make 1 parent of 3
union1(4, 1); // make 1 parent of 4
union1(1, 0); // make 0 parent of 1

printf("Find(3) = %d\n", find1(3)); // should climb: 3 → 1 → 0 → root

return 0;
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 85
 Definition [collapsing rule] :
 If j is a node on the path from I to its root set parent(j) →root(i) the start
collapsing.
 In Disjoint Set (Union–Find), the find operation locates the root of the set
containing element i.
 The collapsing rule (also called path compression) improves efficiency by
making all nodes on the path point directly to the root.
This flattens the tree → future find operations become almost O(1).
 Definition (your statement):
 If j is a node on the path from i to its root and parent[j] != root(i),
set parent[j] = root(i).
 Meaning:
While searching for the root, compress the entire path.
 If j is a node on the path from i to its root and parent[i] != root(i), then set
parent [j] to root(i).

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 86
int find2(int i)
{
/* find the root of the tree containing element i.
Use the collapsing rule to collapse all nodes from i to root */
int root, trail, lead;
// Step 1: Find the root
for (root = i; parent[root] >= 0; root = parent[root]) ;
// Step 2: Path compression (collapsing rule)
for (trail = i; trail != root; trail = lead) {
lead = parent[trail];
parent[trail] = root; // collapse node toward root
}
return root;
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 87
 How It Works
 Step 1 → Find the root
 Move upward until a node has parent[root] < 0.
This is the root.
 Step 2 → Apply collapsing rule
 All nodes from i to the found root will now directly point to root.
 Example before collapsing:
 i → 4 → 2 → 0 (root)
 After collapsing: Why Collapsing Rule is Important?
Makes find nearly constant timeEnsures
 i→0 that future finds are extremely fastUsed
 4→0 with union by rank/size for optimal
efficiencyTime complexity
 2→0
becomes:O(α(n)),where α is the inverse
 The tree becomes flat. Ackermann function (almost constant!)

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 88
Application to equivalence classes

 The equivalence classes to be generated may be regarded as set.

 These sets are disjoint since no polygon can be in two equivalence
classes.
 Initially, all n polygons are in an equivalence class of their own; thus
parent{i} = -1, 0 < =i < n.
 If an equivalence pair, i = j, is to be processed,
 we must first determine the sets containing i and j.
 If they are different, then we replace the two sets by their union.
 If the two sets are the same, then we do nothing since the relation i =
j is redundant: I and j are already in the same equivalence class.
 To process each equivalence pair, we need to perform two finds and
at most one union.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 89
 Given a set of elements and a list of equivalence pairs (like “a is equivalent to
b”), we must form equivalence classes.
 Example:
 If we know
 (1, 2), (2, 5), (3, 7), (6, 7)
 We must produce the equivalence classes:
 {1, 2, 5}
 {3, 7, 6}
 Algorithm to form equivalence classes
 Input
 n elements
 A set of equivalence pairs (a, b)
 Steps
1. Initialize parent array (each element is its own class)
2. For every pair (a, b):
→ call union(a, b)
3. After processing all pairs:
→ all elements having the same root belong to the same equivalence class.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 90
Program: Forming Equivalence Classes using Disjoint Set (Collapsing Rule)
#include <stdio.h>
#define MAX 20
int parent[MAX];
/* ---------- FIND with COLLAPSING RULE ---------- */
int find2(int i)
{
int root, trail, lead;
/* Step 1: Find the root */
for (root = i; parent[root] >= 0; root = parent[root]);
/* Step 2: Path Compression */
for (trail = i; trail != root; trail = lead) {
lead = parent[trail];
parent[trail] = root;
}

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 91
return root;
}
/* ---------- UNION OPERATION ---------- */
void union_sets(int a, int b)
{
int rootA = find2(a);
int rootB = find2(b);
if (rootA != rootB) {
/* attach rootB under rootA */
parent[rootB] = rootA;
}
}
/* ---------- MAIN PROGRAM ---------- */
int main()
{
int n, m;
int i, a, b;

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 92
 printf("Enter number of elements: ");
scanf("%d", &n);
/* Initialize each element as its own set: parent[i] = -1 */
for (i = 1; i <= n; i++)
parent[i] = -1;
printf("Enter number of equivalence pairs: ");
scanf("%d", &m);
printf("Enter the %d pairs (a b):\n", m);
for (i = 0; i < m; i++) {
scanf("%d %d", &a, &b);
union_sets(a, b);
}
/* ---------- PRINT EQUIVALENCE CLASSES ---------- */
printf("\nEquivalence Classes:\n");
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 93
for (i = 1; i <= n; i++) {
/* Print only roots */
if (parent[i] < 0) {
printf("{ ");
for (int j = 1; j <= n; j++) {
if (find2(j) == i)
printf("%d ", j);
}
Enter number of elements: 3Enter number of
equivalence pairs: 1 2 3 4 3 4 3 3 5 6 7
printf("}\n");
Enter the 1 pairs (a b):
}
} Equivalence Classes:{ 1 }
{23}

return 0;
}
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 94
Counting Binary trees
Distinct Binary tree
 if n = 0 or n = 1, there
is only one binary tree.
If n = 2, then there are
two distinct trees and
if n = 3.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 95
Number of Distinct Binary Trees
A binary tree with n nodes can be arranged in several structurally different ways.
These are counted by the Catalan numbers.
But for small n, we list them manually.

Case n = 0
There is one empty tree.

Case n = 1
There is only one binary tree:
a single root node.

Case n = 2
There are two distinct binary trees.
These correspond exactly to your top image:
Root with left child
Root with right child
Hence, T(2) = 2

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 96
 Case n = 3
 Above image shows five distinct binary trees.
 These are the 5 Catalan structures for n = 3, drawn in the second row of in
picture:
 Left-heavy chain
root → left → left
 Left then right chain
root → left → right
 Full balanced tree
root with both left and right child
 Right then left chain
root → right → left
 Right-heavy chain
root → right → right
 Exactly these five shapes appear in image.
 Therefore: T(3) = 5

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 97
Pseudocode
Algorithm CountBinaryTrees(n)
// T is an array to store number of trees for each number of nodes
Create array T[0..n]
T[0] ← 1 // empty tree
T[1] ← 1 // single node tree
For k ← 2 to n do
T[k] ← 0
For i ← 0 to k-1 do
T[k] ← T[k] + (T[i] * T[k-1-i])
EndFor
EndFor
Return T[n]
EndAlgorithm
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 98
Stack permutations:
 Suppose we have the preorder sequence: ABCDEFGHI and the inorder sequence:
BCAEDGHFI of the binary tree.
 To construct the binary tree from these sequences, we look at the first letter in
the preorder sequence,
 A. This letter must be the root of the tree by definition of the preorder traversal
(VLR.}.
 We also know by definition of the inorder traversal {LVR} that all nodes preceding
A in the inorder sequence (B Q are in the left subtree, while the remaining nodes
{ED GHFI) are in the right subtree.
 Figure 5.49(a) is our first approximation to the correct tree.
 Moving right in the preorder sequence, we find B as the next root.
 Since no node precedes B in the inorder sequence, B has an empty left subtree,
which means that C is in its right subtree.
 Figure 5.49(b) is the next approximation. Continuing in this way, we arrive at the
binary tree of Figure 5.49(c).
 By formalizing this argument (see the exercises for this section), we can verify
that
PREPARED every binary
BY- [Link] BARIK .[Link] hasDEPT
PROFESSOR, a OFunique pair of preorder inorder sequences.
CSE, SIR MVIT 99
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 100
Example: Is 2 1 4 3 5 a
Stack Permutation of Action Stack Input Output

1 2 3 4 5?
PUSH 1 1 2345 –
Next output
needed → 2 (≠ 21 345 –
top=1) → PUSH 2
 Let the input be: POP (top=2
1 345 2
12345 matches output)
POP (top=1
 Goal output: matches next – 345 21
output)
21435 Next output
needed → 4 → 3 45 21
 We try to generate it using a PUSH 3
stack. PUSH 4 43 5 21
POP (top=4
3 5 214
matches output)
POP (top=3
matches next – 5 2143
output)
PUSH 5 5 – 2143
POP – – 21435

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 101
PSEUDOCODE: Check if a Permutation Is a Stack Permutation
Algorithm IsStackPermutation(A[1..n])
// A is the permutation we want to check
Create an empty stack S
input ← 1 // next number available to push
for i ← 1 to n do
x ← A[i] // number we need to output
// Push input numbers until top of stack equals x
while (input <= n) AND ( (S is empty) OR (top(S) ≠ x) ) do
push(S, input)
input ← input + 1
end while
// If top is not x, permutation is impossible
if (top(S) ≠ x) then
return FALSE
end if
pop(S) // output x to match the permutation
end for
return TRUE
EndAlgorithm
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 102
Matrix multiplication
 Suppose that we wish to compute the product of n matrices: M1 * M2 * • • • *
Mn.
 Since matrix multiplication is associative, we can perform these
multiplications in any order.
 We would like to know how many different ways we can perform these
multiplications. For example, if n = 3, there are two possibilities:

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 103
 We want to compute 𝑀1 ∗ 𝑀2 ∗ ⋯ ∗ 𝑀𝑛 .
 Because matrix multiplication is associative:
 𝑀1 ∗ 𝑀2 ∗ 𝑀3 = 𝑀1 ∗ 𝑀2 ∗ 𝑀3
 we can multiply in different orders (i.e., different parenthesizations).
 We want the number of distinct ways to parenthesize 𝑛matrices.

Example: n = 3
 Matrices: 𝑀1 , 𝑀2 , 𝑀3
 Multiply 𝑀1 ∗ 𝑀2 first, then multiply the result by 𝑀3 :
 𝑀1 ∗ 𝑀2 ∗ 𝑀3
 Multiply 𝑀2 ∗ 𝑀3 first, then multiply 𝑀1 by the result:
 𝑀1 ∗ 𝑀2 ∗ 𝑀3
 Total ways = 2

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 104
 Example: n = 4
 Matrices: 𝑀1 , 𝑀2 , 𝑀3 , 𝑀4
 We can split into two parts in three different positions:
 Split after first matrix: 𝑀1 ∗ 𝑀2 ∗ 𝑀3 ∗ 𝑀4
 Split after second matrix: 𝑀1 ∗ 𝑀2 ∗ 𝑀3 ∗ 𝑀4
 Split after third matrix: 𝑀1 ∗ 𝑀2 ∗ 𝑀3 ∗ 𝑀4
 Then, recursively, each subproduct can also be parenthesized differently.
 Total ways = 5

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 105
 The number of distinct ways to obtain M1i
and M1 + I are bi and bn-i, respectively.
Therefore,
 letting
 b 1 = 1, we have

 Then we see that bn is the sum of all the

possible binary trees formed in the following
way: a
 root and two subtrees with bi and bn-i-1
nodes, for 0 < i < n. This explanation says
that

Therefore, the number of binary trees with n nodes, the number of

permutations of 1 to n obtainable with a stack, and the number of
ways to multiply n + 1 matrices are all equal.

PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 106
Number of Distinct binary trees
 To obtain the number of distinct binary trees with n nodes, we must solve the
recurrence

 To begin we let:

 which is the generating function for the number of binary trees. Next observe
that by the recurrence relation we get the identity:

 Using the formula to solve quadratics and the recurrence that B (0) = b0= 1
we get:
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 107
PREPARED BY- [Link] BARIK .ASST. PROFESSOR, DEPT OF CSE, SIR MVIT 108