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.