Sketched solutions. (1) char followPath(treeNode* t, string path) { if (t == NULL || path.length()==0) return '?'; // nothing to search for else { treeNode* temp= t; int i= 0; char nextArc = path[i]; while (i < path.length() && (t!=NULL)) { // follow the path either until the path goes cold, or reach its end. if (nextArc == 'l') {temp= temp->left;} // move along the next arc else {temp= temp->right;} i++; nextArc= path[i];// get the next arc } // on termination check which condition holds if (t==NULL) return '?'; // run out of path... else return t->item; // or reached a valid position. } } (2) Delete i: f / \ c m / \ / \ b e g w / / \ a d z Delete f: g / \ c m / \ \ b e w / / \ a d z Delete a: g / \ c m / \ \ b e w / \ d z 3. BST with maximum height : a linear tree.. BST with minimum height : a balanced tree. 4. void BST::PrintBetween(ptrType Ptr, int l, int r) { if (Ptr != NULL) { if ((Ptr->item <= r) && (l <= Ptr -> item)) { cout << Ptr-> item ; } PrintBetween(Ptr-> LChildPtr, l, r); PrintBetween(Ptr-> RChildPtr, l, r); } } 5. bool search (treeNode* t, int Key) { //POST : returns true iff Key is in the tree treeNode* temp= t; while( t!= NULL && t-> item != Key) { if (t-> item < Key) t= t-> RChildPtr; else t= t-> LChildPtr; } if (t== NULL) return false; else return true; } 6. Overview: search the tree to find the right place to insert. Here's the idea of the pseudo code. void insert(treeNode* t, int Key) { if (t == NULL).. make new node for Key; else {treeNode* temp= t; bool b= true; if ( while( b ){ if (temp -> item < Key) { if (temp -> RChildPtr != NULL) temp= temp-> RChildPtr; else b= false; } else if (temp -> item > Key) { if (temp -> LChildPtr != NULL) temp= temp-> LChildPtr; else b= false; } else if (temp-> item == Key) b = false; } if (temp-> item < Key && temp -> RChildPtr == NULL) .. add node as a right child else if (temp-> item > Key && temp -> LChildPtr == NULL) .. add node as a left child // otherwise do nothing. }