Function to traverse a binary tree

Question

I'm just starting with trees and am writing a function that traverses a binary tree and visits every node. I'm calling a function called doSomething(TreeNode *thisNode) for each node in the tree. I want to make sure if what I have is correct and that I'm on the right track? Thanks!

void MyTree::Traverse(TreeNode *rt)
{

If(rt != NULL)

Traverse(rt -> left);
doSomething (rt);
Traverse(rt -> right);

}

Answer 1

Almost, but not quite.

The if statement in C++ is not capitalized, and you must add brackets as follows:

void MyTree::Traverse(TreeNode *rt)
{
    if(rt != NULL)
    {
        Traverse(rt -> left);
        doSomething (rt);
        Traverse(rt -> right);
    }
}

If you do not add brackets, the statements doSomething(rt) and Traverse(rt->right) will be called no matter if the node is valid or not!

Answer 2

It is always a good idea to debug your program with some relevant test cases. In your code, what do you think would happen if rt is not NULL? This should help you figure out if you are doing it right.