# Tutorial 7 - binary search tree 6 Draw a graph having the...

This preview shows pages 1–3. Sign up to view the full content.

DCS5028 DISCRETE STRUCTURES TUTORIAL 7 1 CHAPTER 7: Trees 1. Refer to the tree diagram below. With “i” as the root w hat is the height of the tree? b i d j k h a e c f g 2. Refer to the tree diagram below. With “a” as the root, what is the height of the resulting tree? d a i g e b j c f h 3. For questions (i-iii), refer to the tree diagram below: a b c d e f h i j k l m n o p q r (i) Find the parents of c and h (ii) Find the ancestors of c and j (iii)Find the children of d and e (iv) Find the descendants of c and e (v) Find the siblingsof f and h (vi) Find the leaf vertices (vii)Find the internal vertices

This preview has intentionally blurred sections. Sign up to view the full version.

View Full Document
DCS5028 DISCRETE STRUCTURES TUTORIAL 7 2 (vii) Draw the subtree rooted at j (xi) Draw the subtree rooted at e 4. Redraw the following tree with V6 as the root: (a) Use the newly drawn three in question 4 to answer the following questions: 1. What are the descendants of V4? 2. List all level-4 vertices. 3. List all internal vertices. 5. Place the words FOUR SCORE AND SEVEN YEARS AGO OUR FOREFATHERS BROUGHT FORTH in the order in which they appear in a
This is the end of the preview. Sign up to access the rest of the document.

Unformatted text preview: binary search tree. 6. Draw a graph having the given properties: Full binary tree, nine terminal (leaf) vertices, height = 3 . Explain why no such graph exists. 7. Given the following alphabets P T D H X M S J B E N K a) Create a binary search tree from the above alphabets. b) Write the traversal for Depth First Search in finding the letter ‘ M ’ based from the answer in question 7(a). c) Write the traversal for Breath First Search in finding the letter ‘ S ’ based from the answer in question 7(a). V2 V1 V3 V4 V5 V8 V6 V9 V7 V10 DCS5028 DISCRETE STRUCTURES TUTORIAL 7 3 8. Find the minimal spanning tree by using Prim’s algorithm for the graph below: 2 3 1 3 4 2 3 3 2 9. Find the minimal spanning tree by using Kruskal’s algorithm for the graph below: 4 1 12 6 7 5 11 14 8 13 3 9 2 10 10. Based on the tree diagram below, list the order in which the vertices are processed using preorder, inorder and postorder traversal. A B C D E F 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9...
View Full Document

{[ snackBarMessage ]}

### What students are saying

• As a current student on this bumpy collegiate pathway, I stumbled upon Course Hero, where I can find study resources for nearly all my courses, get online help from tutors 24/7, and even share my old projects, papers, and lecture notes with other students.

Kiran Temple University Fox School of Business ‘17, Course Hero Intern

• I cannot even describe how much Course Hero helped me this summer. It’s truly become something I can always rely on and help me. In the end, I was not only able to survive summer classes, but I was able to thrive thanks to Course Hero.

Dana University of Pennsylvania ‘17, Course Hero Intern

• The ability to access any university’s resources through Course Hero proved invaluable in my case. I was behind on Tulane coursework and actually used UCLA’s materials to help me move forward and get everything together on time.

Jill Tulane University ‘16, Course Hero Intern
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://www.coursehero.com/file/14068457/Tutorial-7/", "fetch_time": 1542736001000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2018-47/segments/1542039746528.84/warc/CC-MAIN-20181120171153-20181120192431-00050.warc.gz", "warc_record_offset": 827792289, "warc_record_length": 89098, "token_count": 919, "char_count": 3356, "score": 3.90625, "int_score": 4, "crawl": "CC-MAIN-2018-47", "snapshot_type": "latest", "language": "en", "language_score": 0.8528462648391724, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00057-of-00064.parquet"}