Problem Set 3: Trees and Graphs

Overview: This assignment will cover that material on trees and graphs. Provide the solutions for the problems in this assignment a Microsoft Word document. A Power Point file or scanned handwritten drawings are also fine for Problems 1(a) and 2(a). Remember to include your name and course number within all documents that you submit.

[5 points] Trees

Read the assigned chapter and notes for Week 5 located in the Learning Activities area in Blackboard. Then answer the following questions:

[3 points] Draw a binary tree that produces the inorder traversal for the nodes in the following order: 14, 23, 15, 115, 22, 134, 16, 178, 161, 27, 83, 44, 65.

[2 points] Briefly explain the differences between a binary search tree and a regular binary tree. Which tree has a better advantage over the other? Briefly explain why.

[5 points] Graphs

Read  the  assigned  chapter  and  notes  for  Week  6  located  in  the  Learning  Activities  area  in Blackboard. Then provide solutions to the following problems:

[3 points] Draw the adjacency list for the following graph:

[2 points] Is the graph in Problem 2(a) considered a dense or sparse graph? Briefly explain why. Also, state the mathematical property for both a sparse graph and a dense graph.