I don\'t understand part b because I thought this would be a divide-and-conquer
ID: 3143511 • Letter: I
Question
I don't understand part b because I thought this would be a divide-and-conquer algorithm since it breaks down the problem into two sub problems and continuously does that as stated here
10. 2.35/2.85 points | Previous Answers HunterDM3 5.2.020 Let T be a binary tree whose nodes are elements of some set U. The following algorithm searches T for a target value tEU and returns true if and only if t is a node in T. function Search (tEU, T binary trees)) ifTis empty then return false else if t= the root of then return true else return (search(t, left subtree of T) V Searah (t, right subtree of T)) (a) Write down a top-down evaluation of Search(17, T), where T is the tree in the figure below 27 31 12 17 92 57 71 65 23 search(17, T) = search(17, T27) V Search(17, T31) Search( 17, O) V Search(17, T12) V Search(17, T17) V Search(17, T14) = False , V Search( 17, T92) V Search(17, T57) V true V Search(17, T23) V Search( 17, T88) = | False , V Search( 17, ) V Search(17, ) V Search( 17, O) V Search(17,0) V true V Search( 17, Q) V Search(17) V Search(17, ) V Search( 17, FalseV false V false V false V false V true V false V false V false V false | True (b) Which type of algorithm is this? O divide-and-conquer algorithm traversal algorithm greedy algorithmExplanation / Answer
Divide-and-conquer is a top-down technique for designing algorithms it breaks down the problem into two sub problems after that it will go for search in only one direction (right subtree or left subtree) hoping that the solutions of the subproblems are easier to find.
But here it is going in both direction for search. So thats why it is not Divide-and-conquer.
It is Traversal algorithm because first he will search in left subtree if not match then he will search in right subtree.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.