I am going out of town and don't have access to my professor and / or tutors for the weekend, and we have an assignment involving a BST. I have done all of my insert, remove, and search functions, and went to the tutor about the remaining ones I have, but he is a genius and I don't necessarily "follow" all he is saying all the time.

Anyways, I need help with 3 functions, some of which I have actual code for, others the pseudo-code, which I need further assistance on (not asking for code here, just ideas/clarification).
Here is the class implementation provided:

//bst.h typedef int T; class BST {
public: BST(); //constructor
~BST(); //destructor bool empty();
bool search(const T& item); 
void insert(const T& item); 
void remove(const T& item); 
int level(const T& item); 
void leveltraversal(ostream& out); 
void nonrecurs_preorder(ostream& out); 
int height();
private: class BinNode {
public: T data;
// non-recursive
BinNode* left; BinNode* right; BinNode() : left(0), right(0) {} BinNode(T item): data(item), left(0), right(0) {}
}; typedef BinNode* BinNodePtr; BinNodePtr myRoot;

And now for my questions:


int level(const T& item);

- Write a function member level() which determines the level of an given item in the tree. The root of the BST is at level 0, and its children are at level 1, and so on.
-- I have a general idea of this, which would be just do do a typical search of the item passed into the function, but add a counter that increments every time we go to a right or a left subtree.


int height();

-Write a member function height() to return the height of a tree
--This is probably my most problematic function, I got help from the tutor, and we worked a little something out. I know that I need to do this recursively via a helper function:

int privateHeight(BinNodePtr subRoot);

--Within this function I know that I need to initialize some height variable to 1, and then break into a loop:

int height = 1;
//this is where i fall apart
//I know I need to call the privateHeight() function recursively and compare 
//which of the two sides is larger, in case it is an unbalanced tree, but I dont have the slightest idea 
//on how I would do this :(

return 1 + privateHeight(the larger side);
}//end if
else return 0

3. Sorry this is so long, but here is my last one:

void levelTraversal(ostream& out);

-Write a member function leveltraversal() to traverse a tree level by level; that is, first visit the root, then all nodes on level 1 (children of the root), then all nodes on level 2, and so on. Nodes on the same level should be visited in order from left to right.
--This one is more to verify that I am on the right track, my code compiles fine, but the passing of ostream& out is throwing me off in my client program when I go to test this, does it need to be done differently with another helper function? I didn't think so since we are using the STL queue, or maybe I am just having an issue with my main.cpp

void BST::leveltraversal(ostream& out){
	queue<BST::BinNodePtr> myQ;
	if (myRoot == NULL)
	BinNodePtr p = myRoot;
		cout << myQ.front();
		p = myQ.front()->left;
		p = myQ.front()->right;
		cout << myQ.front();

Thanks for your help, sorry for the length of the post

6 Years
Discussion Span
Last Post by peterman.k

Good thing its not due till friday. If you want to get the most out of this sight, you need to post a small question and be 80% of the way done;)


Actually this is only 10% of the assignment, I have provided sufficient coding for the post, and never asked for actual code because I dont like getting the straight answers, if you read my post you will notice that I asked for assistance with the pseudo-code, not the code itself. The only question that I needed help with the c++ code itself was question number three, in which I was running into errors and thought I might have some syntax wrong, which turned out was the case. I'm not just throwing out bait and waiting for free answers from a forum site. I enjoy learning, and would appreciate if something useful was posted instead of restating the rules that I know and am abiding by ;).

No offense meant, just a little frustrated by the assumed naivety.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.