MODULE-3


1. Discuss Threaded Binary Tree. OR Explain Threaded binary trees with suitable examples.


2. Discuss different representations of a graph.


3. What is a Binary Search Tree? Construct a binary search tree for the following elements 11,6,14,8,12,15,16,7,9,23. OR Create a Binary Search Tree for the following data and do Inorder, Preorder and Postorder traversal of the tree. 45, 70,30, 60, 15,75,35,55,20,85,80  OR Draw a Binary expression tree for the following and perform preorder traversal: a * ( b + c ) + ( d * e ) / f + g * h


4. Apply Djkstra’s algorithm on the following graph with Node A as the starting node. OR Apply Djkstra’s algorithm for the following graph with Node S as the starting node.


5. The Preorder traversal of the tree is: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10 The inorder traversal of the tree is : 01,2,3,4,5,6,7,8,9,10 What is the postorder traversal? How can a general tree be converted to a binary tree?


6. A communications network is represented by a graph. Each node represents a communication line and each edge indicates the presence of interconnection between the lines. Which traversal technique can be used to find breakdown in line? Explain.


7. Write a recursive algorithm for computing factorials. Which data structure can be used to implement this algorithm?


8. Perform inorder, postorder and preorder traversals for the following binary tree.


9. Explain the working of the Kruskal’s algorithm


10. Define the following terms with respect to a graph: i) M-ary tree ii) Out Degree iii) Leaf iv) Node, v) Edge, vi) Path vii) Cyclic Graph viii) Siblings ix) Strictly Binary Tree


11. Discuss 1) different representations of a graph 2) height balanced trees. 3) Minimal Spanning Tree. 4) algorithm of Breadth First Search (BFS) traversal for a Graph. Explain with an example.


12. Write an algorithm for 1) deletion of nodes in Linear Linked List (2) INSERT operation to insert a node at a given position in a Link list. (3)  to find the length of a simple link list. (4) to insert a node in a Circular Link List at the FIRST position. (5) DELETE operation in a Binary search tree. (6) a non recursive (Iterative) pre order traversal of Binary search tree.


13.  Explain spanning tree with example


14. List out graph traversal techniques & explain any one using suitable examples.


15. Explain Sequential search method with suitable example.


16. Explain insert and delete operations in AVL trees with suitable examples


17. Create an AVL tree for the following sequence of numbers. Also mention the name of action taken. 200, 400, 800, 900, 850, 700, 950, 100, 150