Tree & Graph problems

Tree & Graph problems

From Data Structures

Multiple Choice

Find the post-order Traversal

• a) 6, 2, 5, 7, 11, 2, 5, 9, 4

• b) 6, 5, 2, 11, 7, 4, 9, 5, 2

• c) 2, 7, 2, 6, 5, 11, 5, 9, 4

• d) 2, 7, 6, 5, 11, 2, 9, 5, 4

Multiple Choice

Find the left order traversal

• a) 2, 7, 2, 6, 5, 11, 5, 9, 4

• b) 2, 7, 5, 2, 11, 9, 6, 5, 4

• c) 2, 5, 11, 6, 7, 4, 9, 5, 2

• d) 2, 7, 5, 6, 11, 2, 5, 4, 9

Multiple Choice

For a particular tree, the in-order traversal is 6,2,8,7,11,2,5,9,4 and pre-order traversal is 2,7,2,6,8,11,5,9,4. Find the right child of the root.

• 5

• 7

• 2

• 8

BST

Insertion and Deletion

Insertion

• 10

• 20

• 30
  

• 5
  

• 2

• 1

• 6

  4

Lets see how the values get inserted

https://visualgo.net/en/bst

 Adelson, Velski & Landis Tree

Insertion and Deletion

Insertion

• 10

• 20
  

• 30

• 40

• 50

• 5

• 4
  2
  1

B- Tree

Insertion and Deletion

Insertion with Max Deg 4

10
20
30
40
50
60
15
35
38
39
52

Let's see the insertion... 

https://www.cs.usfca.edu/~galles/visualization/BTree.html

Graph 

Traversal Topologoical Sort

BFS & DFS 

Along with topological sort

Lets see the solution.. 

https://visualgo.net/en/dfsbfs

Heap Tree

Min and Max

Insert and Extract in Heap 

10
20
30
45
48
19
25
35
27

How to insert ? how extraction done?

https://visualgo.net/en/heap

Lets check the understandability of DS

There are 7 systems (0,..,6) connected as given in the figure.What is the minimum number of connections to be added to the network so that when a system goes down, the rest of the network is still connected ?

How many Articulation points are available in this graph? How? 

0

1
2
3

Multiple Choice

The leaf of an expand is never an articulate point

• True

• False

• Cannot be Determined

Multiple Choice

Correct choice of data structures can improve the performance of algorithms. Match the following algorithms with appropriate data structures,

i. Breadth first search

ii. Depth first search

iii. Sorting

a. Heap

b. Stack

c. Queue

• A. i­a ii­b iii­c

• B. i­b ii­a iii­c

• C. i­c ii­b iii­a

• D. i­b ii­c iii­a

Which of the following the graph posses? How?

a) Euler Circuit
b) Euler Path

Quickly decide if its eulerian.

Give Reasons

Find if it has Euler Path or not

If it has, how many edges are required to be added, to make this an euler circuit?