iterbfssametree.cpp

#include <iostream>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) {
        val = x;
        left = nullptr;
        right = nullptr;
    }
};

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // Manual queue for BFS
        TreeNode* queue1[1000];  
        TreeNode* queue2[1000];  
        int front1 = 0, rear1 = 0;
        int front2 = 0, rear2 = 0;

        queue1[rear1++] = p;  
        queue2[rear2++] = q;  

        while (front1 < rear1 && front2 < rear2) {
            TreeNode* node1 = queue1[front1++];
            TreeNode* node2 = queue2[front2++];

            if (!node1 && !node2) continue; // Both NULL, move to next
            if (!node1 || !node2) return false; // One NULL, other not
            if (node1->val != node2->val) return false; // Values mismatch

            queue1[rear1++] = node1->left;
            queue1[rear1++] = node1->right;
            queue2[rear2++] = node2->left;
            queue2[rear2++] = node2->right;
        }

        return front1 == rear1 && front2 == rear2;
    }
};

// Function to build a tree (Manual input)
TreeNode* buildTree() {
    int val;
    cin >> val;
    if (val == -1) return nullptr;  // Use -1 as NULL marker

    TreeNode* root = new TreeNode(val);
    root->left = buildTree();
    root->right = buildTree();

    return root;
}

int main() {
    cout << "Enter first tree (-1 for NULL nodes): ";
    TreeNode* p = buildTree();
    cout << "Enter second tree (-1 for NULL nodes): ";
    TreeNode* q = buildTree();

    Solution sol;
    if (sol.isSameTree(p, q))
        cout << "true" << endl;
    else
        cout << "false" << endl;

    return 0;
}