bfs.cpp

#include <iostream>
#include <queue>
using namespace std;

// Definition for a binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Function to check if two trees are the same using BFS
bool isSameTree(TreeNode* p, TreeNode* q) {
    queue<TreeNode*> queueP, queueQ;

    queueP.push(p);
    queueQ.push(q);

    while (!queueP.empty() && !queueQ.empty()) {
        TreeNode* nodeP = queueP.front();
        TreeNode* nodeQ = queueQ.front();
        queueP.pop();
        queueQ.pop();

        // Check if both nodes are null
        if (!nodeP && !nodeQ) continue;

        // Check if only one is null or values differ
        if (!nodeP || !nodeQ || nodeP->val != nodeQ->val) return false;

        // Add child nodes to the queues
        queueP.push(nodeP->left);
        queueP.push(nodeP->right);

        queueQ.push(nodeQ->left);
        queueQ.push(nodeQ->right);
    }

    return queueP.empty() && queueQ.empty(); // Both queues must be empty
}

// Helper function to create a new tree node
TreeNode* newNode(int val) {
    return new TreeNode(val);
}

int main() {
    // Create two sample trees
    TreeNode* p = newNode(1);
    p->left = newNode(2);
    p->right = newNode(3);

    TreeNode* q = newNode(1);
    q->left = newNode(2);
    q->right = newNode(3);

    if (isSameTree(p, q)) {
        cout << "The two trees are the same." << endl;
    } else {
        cout << "The two trees are not the same." << endl;
    }

    return 0;
}