CMPT 125 Lecture Notes - Lecture 16: Time Complexity

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 125
• Professor: Igor Shinkar

Document Summary

Lecture 15 part 6 addarraytotree ( array , first , last ) if first <= last mid = (first+last)/2 tree. add( array[mid] ) addarraytotree ( array , first , mid-1 ) addarraytotree ( array , mid+1 , last ) Write an algorithm that given a bst and a number k, outputs all values in the tree that are smaller than k. Idea: use a traversal that starts with low values and continues in the increasing order. Solution 1: print_less_than_k (btnode* root, int k) { if ( root == null ) return true; print_less_than_k (root->left); if (root->data < k) print(root->data); print_less_than_k (root->right); Note that if root->data >=k, then we don t need to print the right subtree (and the root). A better solution: print_less_than_k (btnode* root, int k) { if ( root == null ) return true; print_less_than_k (root->left); if (root->data < k) { print(root->data); print_less_than_k (root->right);