1. a) Consider the following graphs.Indicate which are trees and which are not If a graph...
Question II - Graph Traversal and Minimum Spanning Trees [40 Points] Consider the following graph: B 10 1 4 1 H 9 4 a) Traverse the graph starting from vertex A, and using the Breadth-First Search algorithm. Show the traversal result and the data structure you are using. [10 Points] b) Traverse the graph starting from vertex A, and using the Depth-First Search (Post-order) algorithm. Show the traversal result and the data structure you are using. [10 Points] c) Apply...
1 Binary Search Trees (25 points) Consider the binary tree as shown in Figure 1. 9 5 15 10 17 8 Figure 1: Binary Tree: The letter next to each node (e.g., a, b) denotes the tree node, and the number inside each node is the key. 1.1 Correctness (10 points) Is this binary tree a valid binary search tree? In other words, does it satisfy the binary search tree property? If not, which node(s) violates the binary search tree...
1. Short Questions Given the following data: 30 20 s0 40 10 60 28 Which method will perform better: Binary Search or Binary Search Tree? a) Give explanation as well S pts) b) Draw a binary search tree using the following data (5 pts) (No need to show the steps) 24 60 17 40 S0 20 22 21 c) Give the In-onder, pre-order and post-order search ordering from the tree constructed in part (b) (5 pts) d) Give definition of...
(a) A student believes that Binary Search Trees possess the following property. Suppose we search for a key and the matching node is a leaf node. Let L be the set of all nodes to the left of the search path, P the set of all nodes on the search path, and R be the set of all nodes to the right of the search path. The student claims that any three keys I ∈ L, p ∈ P, and...
in java ..write all complete program from a- e 1. Given the two binary trees below: 14 16 Write a method called swapSubtrees, which swaps all of the left and right subtrees in the above binary trees. Add this method to the class BinaryTree and create a program to test this method for these 2 trees. Show the original trees and the resulting trees. Note: To test your algorithm, first create a binary search tree. Write a method called singleParent,...
4. Consider the following graph: 2 . Starting from node B, please copy the above picture as many times as needed and, for each approach to building a spanning tree below, (a) draw the tree and (b) Show (by writing a number next to each node) the order in which nodes are added to the tree during its construction: a. Dijkstra's spanning tree (2 points) b. Prim's spanning tree (2 points) c. Depth-first tree (2 points) d. Breadth-first tree (2...
5. Consider the following binary search trees. Try to color them as valid red-black trees. If not possible, please explain. Consider the dummy leaf nodes as well.
discrete 2 question 31 For Esercises 25.28, write the nodes in a breadth first search of the graph for Exercises 21 the node specified 25、 26, g 20. In the computer network in the accompanying figure, the same message is to be broade Dribe ( 21-24 28. e 27. to nodes 4.Е. F and G. One way to do this is to find the shortest path from C to send out multiple copies of the same message. A more etficient...
QUESTION 9 Consider the following binary search tree: If the root node, 50, is deleted, which node will become the new root? A 15 B 24 C 37 D 62 QUESTION 10 In the following trees EXCEPT______, the left and right subtrees of any node have heights that differ by at most 1. A complete trees B perfect full trees C balanced binary trees D binary search trees QUESTION 11 A perfect full binary tree whose height is 5 has...
1. Consider the directed graph on the right side of the following page and complete the exercises below. When conducting a search, be very careful (since a small error early on can result in a large deduction of marks), and whenever you have a "choice" of which adjacent vertex to consider, you must consider the vertices in numerical order from least to greatest. (10 marks total) a. Provide an adjacency list representation of this graph. b. Compute the depth-first search...