Same Tree

struct NodePair {
    TreeNode* left;
    TreeNode* right;
};
class Solution {
public:
    Solution() {}
    ~Solution() {}
    bool isEqual(TreeNode* left, TreeNode* right) {
        if (!left && !right) return true;
        if (!left || !right) return false;
        if (left->val != right->val) return false;
        return true;
    }
    bool isSameTree(TreeNode* left, TreeNode* right) {
        queue<NodePair> nodes;
        nodes.push({left, right});
        while (!nodes.empty()) {
            NodePair top = nodes.front();
            nodes.pop();
            left = top.left;
            right = top.right;
            if (!isEqual(left, right)) return false;
            if (left) {
                if (!isEqual(left->left, right->left)) return false;
                nodes.push({left->left, right->left});
                if (!isEqual(left->right, right->right)) return false;
                nodes.push({left->right, right->right});
            }
        }
        return true;
    }
};

The provided C++ code defines a function to determine if two binary trees are structurally identical and have the same node values. Here's an overview of the solution approach:

• A NodePair struct is used to pair corresponding nodes from the two trees for comparison.
• The Solution class contains two methods:
  • isEqual(TreeNode* left, TreeNode* right): This method returns true if both nodes are NULL (indicating corresponding structure in both trees at that point), or if both are non-null and their values are equal. It returns false otherwise.
  • isSameTree(TreeNode* left, TreeNode* right): This is the main method using a queue to hold node pairs for breadth-first traversal of both trees simultaneously. The method uses the queue to process each paired node:
    • It extracts the top node pair from the queue for comparison using isEqual.
    • If any pair of nodes does not match, the function immediately returns false.
    • If nodes are valid and their paired children have not been enqueued for comparison yet, the corresponding child nodes are enqueued.

The implemented logic ensures only potentially matching nodes are enqueued for comparison by repeatedly checking node pairs in a breadth-first fashion. If all comparisons pass, the function concludes the trees are the same and returns true; otherwise, it returns false as soon as a discrepancy is found. This approach efficiently compares trees by levels, ensuring an accurate and prompt determination of whether the two trees are the same structurally and in value.

class Solution {
    public boolean nodesMatch(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) return true;
        if (node1 == null || node2 == null) return false;
        if (node1.val != node2.val) return false;
        return true;
    }

    public boolean isEquivalentTree(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) return true;
        if (!nodesMatch(node1, node2)) return false;

        ArrayDeque<TreeNode> queue1 = new ArrayDeque<TreeNode>();
        ArrayDeque<TreeNode> queue2 = new ArrayDeque<TreeNode>();
        queue1.addLast(node1);
        queue2.addLast(node2);

        while (!queue1.isEmpty()) {
            node1 = queue1.removeFirst();
            node2 = queue2.removeFirst();

            if (!nodesMatch(node1, node2)) return false;
            if (node1 != null) {
                if (!nodesMatch(node1.left, node2.left)) return false;
                if (node1.left != null) {
                    queue1.addLast(node1.left);
                    queue2.addLast(node2.left);
                }
                if (!nodesMatch(node1.right, node2.right)) return false;
                if (node1.right != null) {
                    queue1.addLast(node1.right);
                    queue2.addLast(node2.right);
                }
            }
        }
        return true;
    }
}

This solution provides a method to determine if two binary trees are identical (same structure and values). It involves the following steps:

1. Define a helper method nodesMatch to compare two nodes:

   • Return true if both nodes are null.
   • Return false if one of the nodes is null, but the other is not.
   • Compare values of the two nodes and return false if they differ.

2. Define the main method isEquivalentTree that initializes two queues for breadth-first traversal of both trees.

3. Enqueue the roots of both trees if they initially pass the nodesMatch test.

4. Use a loop to process nodes level by level:

   • Dequeue the front nodes of both queues.
   • Use nodesMatch to verify the current nodes and their children (left and right).
   • If nodes match, enqueue their children for subsequent rounds of comparison.

5. If all nodes match throughout the traversal, return true indicating both trees are the same. If any discrepancy is found, return false.

The solution leverages a breadth-first search (BFS) approach utilizing a queue data structure, ensuring that each pair of corresponding nodes from the two trees is compared effectively. This ensures that the method is capable of handling large and complex tree structures with efficiency.

struct Pair {
    struct TreeNode *first;
    struct TreeNode *second;
};
typedef struct Element {
    struct Pair pair;
    struct Element *next;
} Element;
typedef struct FIFO {
    Element *front;
    Element *back;
} FIFO;
void push(FIFO *fifo, struct TreeNode *first, struct TreeNode *second) {
    if (!fifo->front) {
        fifo->front = fifo->back = malloc(sizeof(Element));
        fifo->front->pair.first = first;
        fifo->front->pair.second = second;
        fifo->front->next = NULL;
    } else {
        fifo->back->next = malloc(sizeof(Element));
        fifo->back = fifo->back->next;
        fifo->back->pair.first = first;
        fifo->back->pair.second = second;
        fifo->back->next = NULL;
    }
}
void pop(FIFO *fifo, struct TreeNode **first, struct TreeNode **second) {
    if (fifo->front) {
        Element *temp = fifo->front;
        *first = temp->pair.first;
        *second = temp->pair.second;
        fifo->front = fifo->front->next;
        free(temp);
    }
}
bool fifo_is_empty(FIFO *fifo) { return fifo->front == NULL; }
bool nodes_equal(struct TreeNode *first, struct TreeNode *second) {
    if (!first && !second) return true;
    if (!first || !second) return false;
    if (first->val != second->val) return false;
    return true;
}
bool compareTrees(struct TreeNode *first, struct TreeNode *second) {
    FIFO queue = {NULL, NULL};
    push(&queue, first, second);
    while (!fifo_is_empty(&queue)) {
        struct TreeNode *firstNode, *secondNode;
        pop(&queue, &firstNode, &secondNode);
        if (!nodes_equal(firstNode, secondNode)) return false;
        if (firstNode) {
            push(&queue, firstNode->left, secondNode->left);
            push(&queue, firstNode->right, secondNode->right);
        }
    }
    return true;
}

This summary explains how to determine if two binary trees are structurally identical and have the same node values using a Breadth-First Search (BFS) approach in C.

• The provided C code defines a custom FIFO (First In, First Out) queue to facilitate the BFS traversal of both trees simultaneously.
• Two main structs are defined:
  • struct TreeNode - Represents an individual node of the tree. Ensure to have this struct defined elsewhere in your program.
  • struct FIFO - Manages the FIFO queue with helper functions such as push, pop, and fifo_is_empty.
• The function push - Adds a pair of nodes (one from each tree) to the queue.
• The function pop - Removes and returns the front pair of nodes from the queue.
• nodes_equal - Checks if two nodes are equal. Returns true if both nodes are null, have the same value, and false otherwise.
• compareTrees - The main function that uses the FIFO queue to traverse both trees level by level.
  1. Initializes the FIFO queue and pushes the roots of both trees.
  2. Uses a while loop to continue processing as long as the queue is not empty.
  3. Inside the loop, pops the front pair of the queue and checks if the nodes are equal using the nodes_equal function. If they are not equal, returns false.
  4. If nodes are equal and not null, it pushes their left and right children to the queue for subsequent comparison.

By following the BFS algorithm and using a queue to manage simultaneous traversal, this solution effectively compares two binary trees for structural and value equality. If both are identical in structure and node values, the function compareTrees returns true; otherwise, it returns false.

function compareTrees(tree1, tree2) {
    const areEqual = (node1, node2) => {
        if (node1 === null && node2 === null) return true;
        if (node1 === null || node2 === null) return false;
        if (node1.val !== node2.val) return false;
        return true;
    };
    const queue = [[tree1, tree2]];
    while (queue.length) {
        [tree1, tree2] = queue.shift();
        if (!areEqual(tree1, tree2)) return false;
        if (tree1) {
            queue.push([tree1.left, tree2.left]);
            queue.push([tree1.right, tree2.right]);
        }
    }
    return true;
}

This solution defines a function compareTrees written in JavaScript to determine whether two binary trees are the same. The function examines both structure and node values. Understand this step-by-step implementation:

1. The areEqual helper function verifies if two nodes are identical. It returns true if both nodes are null, indicating that both branches are equally terminated. The function returns false if one of the nodes is null, meaning only one tree has ended, or if the values of the nodes differ.

2. Utilize a queue initialized with a pair containing the roots of both trees to employ a breadth-first traversal approach.

3. Process each pair in the queue:

   • Extract the front pair from queue and compare the two nodes using areEqual.
   • If they aren't equal, the function immediately returns false.
   • If nodes are not null, their child nodes (left and right) are added to the queue for subsequent comparison.

4. If the loop concludes without finding inequalities, the function returns true, signifying that both trees are identical.

This implementation efficiently checks tree equality by processing nodes level-wise and terminates as soon as a difference is detected, optimizing performance. Use this function to effectively determine if two binary trees are the same in terms of both structure and data.

from collections import deque

class Solution:
    def compareTrees(self, t1: TreeNode, t2: TreeNode) -> bool:
        def nodesEqual(n1: TreeNode, n2: TreeNode) -> bool:
            if not n1 and not n2:
                return True
            if not n1 or not n2:
                return False
            if n1.val != n2.val:
                return False
            return True
        
        queue = deque([(t1, t2)])
        while queue:
            n1, n2 = queue.popleft()
            if not nodesEqual(n1, n2):
                return False
            
            if n1:
                queue.append((n1.left, n2.left))
                queue.append((n1.right, n2.right))

        return True

This Python solution checks if two binary trees are the same. It defines a class Solution with the method compareTrees, which employs a level-order traversal (using a queue) to compare each corresponding node of the two trees. Here's the breakdown of the process:

• The internal helper function nodesEqual checks if the current nodes n1 and n2 are equivalent:

  • Returns True if both nodes are None.
  • Returns False if one of the nodes is None and the other isn't, or their values differ.

• A deque is initialized and holds tuples, each containing a pair of nodes from the two trees.

• The method proceeds in a loop where nodes are dequeued and compared using nodesEqual. If the nodes differ, the method immediately returns False.

• For each node comparison that passes:

  • Enqueue the left children of both nodes.
  • Enqueue the right children of both nodes.

• If all comparisons pass (i.e., there are no mismatches throughout the traversal), the method returns True, indicating both trees are identical.

This approach ensures all corresponding nodes and subtrees are checked systematically using breadth-first traversal, making the comparison process both thorough and efficient.