Stepik 3.3-3.4

pdf

School

University of California, San Diego *

*We aren’t endorsed by this school

Course

100

Subject

Computer Science

Date

Jul 3, 2024

Type

pdf

Pages

Uploaded by UltraCapybara720

3.3 Binary Search Trees 11 out of 11 steps passed 5 out of 5 points received EXERCISE BREAK: Which of the following are valid Binary Search Trees? (Select all that apply) Select all correct options from the list Cortact ancwar Trom B3 leamers . Total 51% of tries are correct Q All is correct. v Choice A Choice B Choice C Choice D

3.3 Binary Search Trees 11 out of 11 steps passed 5 out of 5 points received EXERCISE BREAK: What is the space complexity of a Binary Search Tree with n elements? Select one option from the list Correct answer from 54 learners Total 61% of tries are correct Q Great work! 0(1) O(log n) e O(n) O(n * log n) 0(n?) Your submissions You got: 1 point out of 1 3.3 Binary Search Trees 11 out of 11 steps passed 5 out of 5 points received EXERCISE BREAK: What is the worst-case time complexity of the find operation of a Binary Search Tree with n elements? Select one option from the list Correct answer from 47 learners Q Good news for you, correct! Total 58% of tries are correct o(1) O(log n) e O(n) O(n * log n) Your submissions You got: 1 point out of 1

3.3 Binary Search Trees 11 out of 11 steps passed 5 out of 5 points received EXERCISE BREAK: What is the worst-case time complexity of the find operation of a balanced Binary Search Tree with n elements? Select one option from the list Q Fabulous answer. Your submissions You got: 1 point out of 1 Correct answer from 47 learners Total 81% of tries are correct

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CODE CHALLENGE: Printing the Elements of a Binary Search Tree in Sorted Order We have defined the following C++ class for you: class Node { public: string label; Nodex parent = NULL; Node* leftChild = NULL; Nodex rightChild = NULL; Ly The equivalent Python class is the following: class Node: def __init__(self): self.label = None self.parent = None self.leftChild = None self.rightChild = None Write a function sortedPrint(Node* node) that recursively prints the labels of all nodes in the subtree rooted at node in ascending sorted order. For example, if we had a tree with some root node root, then calling sortedPrint(root) would print the labels of all nodes in the tree in ascending sorted order. Print a single label per line. You can assume that the Binary Search Tree structure is valid (i.e., all nodes are larger than all of their descendants in their left subtree and smaller than all of their descendants in their right subtree). HINT: Judging by the structure of a Binary Search Tree, does one of the rooted binary tree traversal algorithms (pre-order, in-order, and post- order) seem useful in this context? HINT: What happens if one of the two child pointers is NULL? The tree represented by the Sample Input has been reproduced below for clarity: Sample Input: Cherry -> Apple Cherry -> Lemon Lemon -> Imbe Lemon -> Nectarine Nectarine -> Mango Sample Output: Apple Cherry Imbe Lemon Mango Nectarine Write a program, test using stdin — stdout OrTact anmer fiom 29 learners Total 65% of tries are correct Q Absolutely right. ries are corr Now you have access to the Forum of Solutions where you can discuss your solution with others. 1 void sortedPrint(Nodex node) { if(node == nullptr) return; sortedPrint(node->leftChild); cout << node->Llabel << endl; sortedPrint(node ->rightChild); Next step Solve again

3.4 BST Average-Case Time Complexity 10 out of 10 steps passed 3 out of 3 points received EXERCISE BREAK: Using the same numbering scheme as discussed on the previous step (where the root has a depth of 1), fill in the table below with the depth of each node in the following tree: Tick the right boxes Correct answer from 21 learners Q Yes! Total 100% of tries are correct Depth =1 Depth =2 Depth=3 Node A e Node B ® Node C o Node D o Node E °

3.4 BST Average-Case Time Complexity 10 out of 10 steps passed 3 out of 3 points received EXERCISE BREAK: What is the total depth of the following tree? Enter a number Correct answer from 17 learners Total 20% of tries are correct Q Great! You've solved a complex problem, congratulations! Now you can help other learners in comments by answering their questions, or compare your solution with others on solution forum. Your submissions You got: 1 point out of 1 3.4 BST Average-Case Time Complexity 10 out of 10 steps passed 3 out of 3 points received EXERCISE BREAK: Recall that, in the previous step, based on one of our two initial assumptions, we derived that the probability that a BST with n nodes has exactly i nodes in its left subtree is P,,(z' ) = % Which of our two initial assumptions was this based on? Select one option from the list Correct answer from 18 learners Total 62% of tries are correct Q Correct. All n elements are equally likely to be searched for e All n! possible insertion orders are equally likely Your submissions You got: 1 point out of 1

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Related Documents

Synchronous Session Week 5 - Copy.docx

project3.pdf

IMG_7072.png

image.jpg

TaxPrep Instructional Assignment 2.docx

L05 Check Your Understanding 1: [23FA] CAS 100A, Sec 02: Eff Speech (WC, Bedell).pdf

hw01Task.pdf

Screenshot 2023-12-12 at 9.28.45 AM.png

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

EBK JAVA PROGRAMMING

Computer Science

ISBN:9781337671385

Author:FARRELL

Publisher:CENGAGE LEARNING - CONSIGNMENT

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

New Perspectives on HTML5, CSS3, and JavaScript

Computer Science

ISBN:9781305503922

Author:Patrick M. Carey

Publisher:Cengage Learning

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
New Perspectives on HTML5, CSS3, and JavaScript
Computer Science
ISBN:9781305503922
Author:Patrick M. Carey
Publisher:Cengage Learning