Lab on Data Structure: Practical Unit 5

Table of Contents

1. Task 14: Binary Search Tree (BST) Operations
2. Tasks 18-21: Specialized Matrix Implementations
3. Tasks 22-23: Threaded Binary Trees & AVL Trees
4. Final Lab Exam Summary

1. Task 14: Binary Search Tree (BST) Operations

Assignment: WAP to create a BST and include: Insertion (Recursive/Iterative), Deletion (by Copying/Merging), Searching, Traversals (Recursive/Iterative), Level-by-level Traversal, Mirror Image, and Tree Comparison.

Implementation Requirements

Deletion by Copying: Replaces the deleted node with its predecessor or successor's value.
Deletion by Merging: Attaches the right subtree of the node to the rightmost node of the left subtree.
Level-order Traversal: Uses a Queue to visit nodes level by level.
Height and Counting: Use recursion to count leaf nodes and determine the maximum depth.

2. Tasks 18-21: Specialized Matrix Implementations

Assignment: Implement Diagonal, Lower Triangular, Upper Triangular, and Symmetric Matrices using a 1D array.

To save memory, specialized matrices store only non-zero elements in a one-dimensional array.

Matrix Type	Storage Condition (Row i, Col j)	1D Mapping Index (Row-Major)
Diagonal	Only i = j stored.	index = i
Lower Triangular	Only i >= j stored.	index = [i * (i + 1) / 2] + j
Upper Triangular	Only i <= j stored.	index = [j * (j + 1) / 2] + i
Symmetric	A[i][j] = A[j][i]. Only one triangle stored.	Same as Lower/Upper triangular.

3. Tasks 22-23: Threaded Binary Trees & AVL Trees

Threaded Binary Trees (Task 22)

Assignment: Create a Threaded Binary Tree as per inorder traversal; implement finding successor/predecessor and inorder traversal.

Logic: Instead of NULL pointers, use "threads" to point to the next node in the inorder sequence.
Benefit: Traversal becomes iterative without needing a stack or recursion.

AVL Trees (Task 23)

Assignment: Implement various operations (Insertion, Deletion, Balancing) on an AVL Tree.

The implementation must include Rotations (LL, RR, LR, RL) to maintain the balance factor between -1 and 1.

4. Final Lab Exam Summary

Key Code to Memorize:

Mirror Image: Swap left and right pointers of every node recursively.
Tree Equality: Check if data matches AND left/right subtrees are equal recursively.
Matrix Indexing: The formulas for mapping 2D coordinates to 1D arrays are high-frequency viva questions.

Frequently Asked Questions

Q: What is the difference between Deletion by Copying and Deletion by Merging?
Copying maintains the tree's height better, while Merging is simpler to implement but can lead to very skewed (unbalanced) subtrees.

Q: Why store a Symmetric Matrix in a 1D array?
Since A[i][j] is the same as A[j][i], storing both is redundant. A 1D array reduces space usage by nearly 50%.