How can I return a bool in a recursive implementation of depth first search?

Question

I want to write a function to check if two binary trees are the same.

The code looks like:

bool checkSame(Node* first, Node* second) {
    // Check if nodes are the same

    // Check left nodes: checkSame(first->left, second->left)
    // Check right nodes: checkSame(first->right, second->right)

}

The issue is that I'm not sure what to return here. All the implementations of DFS I've found have a void return value. Is there one where it returns a bool?

Also, I'm looking for a recursive solution, not an iterative one.

Answer 1

You do it in exactly the same way as if you were calling some other functions instead of recursing.
(Recursion's big secret is that there's nothing special about recursion.)

The trees are equal if and only if

• the nodes are equal, and
• both its subtrees are equal

so

return first->data == second->data 
    && checkSame(first->left, second->left)
    && checkSame(first->right, second->right);

Handling the empty cases left as an exercise.