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

Question

I want to write a function to check if two binary trees match.

The code looks like this:

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 problem is that I'm not sure what to return here. All the DFS implementations I found have a void return value. Is there where it returns a bool?

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

Answer 1

You do this exactly as if you were calling other functions instead of recursion.
(Recursion is the big secret that there is nothing special about recursion.)

,

• ,

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

, .