Same Tree

Description

Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example

Code

#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    bool recursive(TreeNode *p, TreeNode *q)
    {
        if (!p && q || p && !q || p->val != q->val)
            return false;
        else if (!p && !q)
            return true;

        if (recursive(p->left, q->left) == false)
            return false;
        if (recursive(p->right, q->right) == false)
            return false;
    }

    bool isSameTree(TreeNode *p, TreeNode *q)
    {
        if (recursive(p, q))
            return true;
        return false;
    }
};

Thought

I thought it was a kind of DFS problems. The reason of the thought was I should compare the two different tree's node from the root and traverse them in same order. So one of the best way to traverse two given trees is preorder traverse because I should start iterate from the root node. (I think I can solve it by BFS)
For a Graph, the complexity of a Depth First Traversal is O(n + m), where n is the number of nodes, and m is the number of edges.

Since a Binary Tree is also a Graph, the complexity of each of these Depth-first traversals is O(n+m). (n is a number of nodes, m is a number of edges)
Since the number of edges that can originate from a node is limited to 2 in the case of a Binary Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the total number of nodes.

The complexity then becomes O(n + n-1), which is O(n).