Scribd
Upload
25 views2 pages

Tutorial 8

The document contains a tutorial for Discrete Mathematics (MA105) at Jaypee University, focusing on rooted trees and their properties. It includes questions about identifying internal vertices, leaves, parent-child relationships, and traversal orders for given trees. Additionally, it discusses creating binary search trees, representing expressions as binary trees, and calculating minimum spanning trees using Kruskal's and Prim's algorithms.

Uploaded by

divyansh9092
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
25 views2 pages

Tutorial 8

The document contains a tutorial for Discrete Mathematics (MA105) at Jaypee University, focusing on rooted trees and their properties. It includes questions about identifying internal vertices, leaves, parent-child relationships, and traversal orders for given trees. Additionally, it discusses creating binary search trees, representing expressions as binary trees, and calculating minimum spanning trees using Kruskal's and Prim's algorithms.

Uploaded by

divyansh9092
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Jaypee University of Engineering &Technology, Guna]

Diserete Mathematies (MA105) Tutorial 8,


(B.Tech. Ist year llnd Semester),

1. AnsWer these qwstions about the rooted tree illustrated.


Which tNis the not?
(a) Which verticesare intemal?
()Which verties arr leaves?
() Which verties ar children ofi?
(a) Which vertex is the parent of h? h
(e) Which ar siblings of o?
( Which verties ae ancestors of m?
)Which vertices ar descendants of b?

2 Consider the following trees


9.

Tree 2 Tree 3
Tree l

traversal visits the vertices of the


(2) Detemine the order in which a preorder
above rooted trees.
visits the vertices of the
6) Detemine the order in which an inorder traversal
zbove rooted trees.
visits the vertices of the
(c) Determine the order in which a postorder traversal
sbove rooted trees.

8, 4, 39, 77. Create a binary


3. Givea a sequeace of numbers 19, 25, 6, 9, 11, 21, 47,
searca tree for the sequence.
the prefix and postfix forms of
4. Represent the expression as a binary tree and write
te expression
i) (z+b)(c-d) ii)(a+b)*ctd)°e)-(atb)*c-d)
statues that has many visitors each day.
3. a New York, ther is a park with famous shown) with the places being
Lignting is to be installed at 5 places in the park (as
following the given paths, The
connected eiher directly or indirectly by cablingbetween cach light.
v2lzes cn each edge represent the distance (in m)
shortest length of cabling required and show the minimum
(a) Calculate the
spanning tree (MST). and Prim's algorithm for
between Kruskal's algorithm
(b) State two differences
finding a minimum spanning tree.

sprinkler system in the given diagram. Using


a gardener and has created a sprinklers with
6. Pauline is that willconnect all of the
Prim'salgorithm, determineandthe network length of piping necded. Each
determine the total in
the least amount of piping and the weight of each edge represents the distance
vertex represents a sprinkler
metres.

You might also like