Class Notes (808,652)
Canada (493,325)
CMPT 225 (60)
John Edgar (28)

CMPT 225 Week 9 Lecture 1

2 Pages
Unlock Document

Simon Fraser University
Computing Science
CMPT 225
John Edgar

Traversals (+ recursion) void print(Node* nd) { if (nd != null) { print(nd->leftChild); cout << << endl; print(nd->right); } } In order traversal. How can you determine size with a traversal? Increment size as you traverse. At least 2 ways of doing this. 1st Way: // public wrapper function int size() const { return postOrderSize(root); // private function which does all the work } int postOrderSize(Node* nd) const { if (nd != null) { int left = postOrderSize(nd->leftChild); int right = postOrderSize(nd->rightChild); return left + right + 1; } return 0; // when reach null child, say nothing there (Base Case) } 2nd Way: Note: apparently this is broken int size() const { postOrderSize(root, 0); } int postOrderSize(Node* nd, int result) const { if (nd != null) { postOrderSize(nd->left, result); postOrderSize(nd->right, result); result++; } return result; } For a tree with n nodes, this will return 1. result is local to recursive call. What you do further down the tree has no impact on root's result. Re
More Less

Related notes for CMPT 225

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.