You may find these recurrences and solutions useful in answering questions.
Recurrence | Solution |
---|---|
T(n) = T(n/2) + O(1) | O(log n) |
T(n) = T(n/2) + O(n) | O(n) |
T(n) = 2T(n/2) + O(1) | O(n) |
T(n) = 2T(n/2) + O(n) | O(n log n) |
T(n) = T(n-1) + O(1) | O(n) |
T(n) = T(n-1) + O(n) | O(n^{2}) |
T(n) = 2T(n/2) + O(1) T(0) = O(1)Use the comments to guide you in writing the function and see the code for balanceHelper above.
TreeNode * deepHelper(TreeNode * t, int& height) // post: (return via reference) height = height of tree rooted at t // returns pointer to deepest leaf in t { if (t == 0) { // could happen, be safe height = 0; return 0; } if (isLeaf(t)) { // I'm a leaf return myself and my height // fill in values here // fill in values here } // define int variables for heights via recursive calls // define Tree pointers for leaves via recursive calls // make two recursive calls // set height = 1 + max of two recursive call values // using computed heights, determine which leaf to return } TreeNode * deepLeaf(TreeNode * t) // post: return deepest leaf in t { int height; return deepHelper(t, height); }