Thread: Binary Trees?

Hello everyone! First post here, so please be gentle.

I am working on a Binary Search Tree for my final project in CS242. At first it didn't seem to bad, and I finished the preorder/inorder/postorder traversals without a hitch.

But now that I'm working on the level order traversals and I'm having a really hard time just starting out.

I got about this far:

Code:

void SearchTree:: level_by_level()
{
	TreeNode *tmpright, *tmpleft;
	tmpright = root->right;
	tmpleft = root->left;
	while(count < height())
	{
		for(int i = 0; i<=count; i++)
		{

		}
		for(int j = 0; j<=count; j++)
		{

		}
	}
}

But I think I am going about this the completely wrong way. Would you guys recommend doing a recursive call? I did a recursive call for the other traversals, but I wouldn't even know how to start the call on this one.

The reason I made the tmpleft and right is because I was going to go down the tree from the root and then output the node each time. But it doesn't seem like that's going to happen very easily.

I don't want someone to do it, I really just want someone to throw some ideas at me and see if I can get it myself. It's not learning if someone fills it out for me.

Thanks guys, I really appreciate you at least looking at it.

Use a small tree as an example, and then write down what you think the order *should* be in the output.

That will help you get your head around it a little better, and it will help to guide you through your work. Don't worry about the height or the count, just use what you know you have at one node. Namely, the node value, and the left and right children (if they exist).

You know you need to output the node value as soon as you see it in the current node. For example, the root node. That should be your first output.

Now, figure out how to save the left and right nodes so that you come across them in the correct order. I think you see that the second output should be the left child of the root node, followed by the right child, the next step is the hard part. How do you get back to the root's left child's left child? Once you can get that, the rest should follow.