Data Structures and Algorithms · Unit 8 · 8 hrs
Trees and Graphs
Exam-focused notes for Trees and Graphs (Data Structures and Algorithms, CSC211): what the TU syllabus asks and how it has actually been tested, with 18 solved past questions from this unit.
What this unit covers
- Concept and Definitions, Basic Operations in Binary Tree, Tree Height, Level and Depth
- Binary Search Tree, Insertion, Deletion, Traversals, Search in BST
- AVL tree and Balancing algorithm, Applications of Trees
- Definition and Representation of Graphs, Graph Traversal, Minimum Spanning Trees: Kruskal and Prims Algorithm
- Shortest Path Algorithms: Dijksrtra Algorithm
AVL tree and Balancing algorithm, Applications of Trees
What is AVL tree? How heap differ from tree? Construct an AVL tree for data 24,12,8,15,35,30,57,40,45 and 78.[10]
An AVL tree, named after Adelson-Velsky and Landis who proposed it in 1962, is a self-balancing binary search tree. It keeps the ordering of a binary search tree, every key in the left subtree of a node being smaller than the node and every key in the right...
Full solved answer →Explain AVL tree with example. Also, explain balancing algorithm for this tree.[10]
An AVL tree (named after inventors Adelson-Velsky and Landis, 1962) is a self-balancing Binary Search Tree (BST) in which the difference between the heights of the left and right subtrees of any node is at most 1. This difference is called the Balance Facto...
Full solved answer →Why do we need to balance the binary search tree? Justify with an example. Create an AVL tree from the data 24, 12, 8, 15, 35, 30, 57, 40, 45, 78.[10]
A binary search tree gives $O(\log n)$ search, insertion and deletion only while its height stays close to $\log2 n$. The shape of the tree, however, depends entirely on the order in which the keys arrive, and nothing in the plain insertion rule prevents it...
Full solved answer →Explain the procedure for construction of Huffman algorithm with example.[10]
Huffman coding is a greedy algorithm used for lossless data compression. It assigns variable-length binary codes to characters based on their frequencies -- characters with higher frequencies get shorter codes and characters with lower frequencies get longe...
Full solved answer →Definition and Representation of Graphs, Graph Traversal, Minimum Spanning Trees
What is the application of spanning tree? Draw a MST of a graph containing any 8 vertices and 11 edges with arbitrary edge costs. [5]
Spanning trees have several important practical applications: 1. Network Design: Used in designing minimum cost communication networks, electrical grids, and computer networks where all nodes must be connected with minimum wiring/cabling cost. 2. Routing Al...
Full solved answer →Write short notes on: a. Breadth First traversal of graph b. TOH [5]
--- Definition: BFS is one of the simplest methods of graph searching/traversal. It explores a graph level by level, visiting all neighbors of a vertex before moving to the next level. Algorithm / Steps: 1. Choose some vertex arbitrarily as the root (starti...
Full solved answer →Find the MST of following graph using Prim's algorithm. [5]
The question asks to find the MST of a graph using Prim's algorithm and provides "the following graph." However, no graph image, vertex list, edge list, or weight values are actually included in the text provided to me. Missing data: - The set of vertices -...
Full solved answer →What is graph traversal? Explain. [5]
Graph traversal (also called graph search) is the process of visiting (checking and/or updating) each vertex in a graph systematically, exactly once. It is a technique used to visit all the nodes of a graph in a specific order, ensuring no vertex is visited...
Full solved answer →What is minimum spanning tree? Explain. [5]
A Minimum Spanning Tree is a connected weighted graph that is a spanning tree having the smallest possible sum of weights of its edges. More formally, given a connected weighted graph G = (V, E), a minimum spanning tree is a subset of edges that: - Connects...
Full solved answer →Discuss depth first and breadth first traversal of a graph with suitable example.[10]
Graph traversal means visiting every vertex of a graph exactly once in a systematic manner. The two standard traversal techniques are: 1. Breadth First Search (BFS) 2. Depth First Search (DFS) --- BFS is one of the simplest methods of graph searching. A ver...
Full solved answer →Discuss the Kruskal's algorithm with example. [5]
Kruskal's algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph. It builds the MST by selecting edges in increasing order of weight, skipping any edge that would form a cycle. --- 1. Sort all...
Full solved answer →Shortest Path Algorithms
Write Dijkstra's algorithm to find shortest path between any two vertices of a graph. [5]
Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph (digraph), assuming no negative weighted edges exist. The shortest distance from source V to any vertex V' is stored in that vertex, and the p...
Full solved answer →What is shortest path? Explain Dijkstra algorithm for finding shortest path using suitable example.[10]
The shortest path between two vertices in a weighted graph is the path whose total sum of edge weights is minimum among all possible paths connecting those two vertices. - It is applicable in directed as well as undirected weighted graphs. - The result give...
Full solved answer →Binary Search Tree, Insertion, Deletion, Traversals, Search in BST
What is binary search tree? Write a program to implement insertion and deletion algorithms in binary search tree.[10]
--- A Binary Search Tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions: - All keys in the left sub-tree of the root are smaller than the key in the root node. - All keys in t...
Full solved answer →How do you traverse a binary tree? Discuss. [5]
Binary tree traversal is the process of visiting each node of a binary tree exactly once in a systematic order. Since a binary tree has three components (root, left subtree, right subtree), different orderings of visiting these components give different tra...
Full solved answer →Illustrate the algorithm for Binary search tree with example.[10]
A Binary Search Tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions: - All keys in the left sub-tree of the root are smaller than the key in the root node. - All keys in the r...
Full solved answer →Differentiate between pre-order traversal and in order traversal. [5]
Binary Tree Traversal means visiting each node in a tree exactly once in a systematic manner. Two of the three popular traversal methods are Pre-order and In-order traversal. --- The pre-order traversal of a non-empty binary tree is defined as follows: 1. V...
Full solved answer →Concept and Definitions, Basic Operations in Binary Tree, Tree Height, Level and Depth
What are the types of binary tree? Compare between them. [5]
A binary tree is a finite set of elements that is either empty or partitioned into three disjoint subsets: the root, the left subtree, and the right subtree, where each subtree is itself a binary tree. --- A binary tree in which every node has either 0 or 2...
Full solved answer →Make Unit 8 stick
Practice CSC211 with flashcards & quizzes