EECS 280 Lecture Notes - Lecture 21: Binary Search Tree, Call Stack, Binary Tree

• School: U of M
• Department: Electrical Engineering And Computer Science
• Course: EECS 280
• Professor: DeOrio

Document Summary

In tail recursive, the compiler automatically knows to reuse the stack frame. When the function returns, the stack frame is removed from the stack. If you call yourself twice in a function, it"s not tail recursive. Ex. void list_print(node *n) { if (n == nullptr) return; cout << n->datum << ; list_print(n->next); //this is tail recursive. the compiler reuses the stack frame. Practice: write print for the tree void tree_print(node *n) { if(n == nullptr) return; list_print(n->left); // not tail recursive - there"s more work so. //a new stack frame is made after this line cout << n->datum << ; list_print(n->right); If you change the order of the sides you print, you get different behaviors. All elements in any left subtree are less than the root and. All elements in any right subtree are greater than the root. In bst search, comparing with the root tells us where to look.