Introduction to Comparison of Two Trees Pattern

In binary tree coding, the Comparison of Two Trees Pattern involves determining if two trees have the same structure and values at corresponding positions. This pattern is crucial in problems where we need to verify if two binary trees are identical or symmetrical. Understanding how to compare each node in both trees helps in solving a wide range of problems, especially those that deal with equality checks between tree structures.

To solve problems based on this pattern, the approach generally involves traversing both trees simultaneously. At each step, the algorithm compares the nodes from both trees. If the nodes are equal, the process continues to their respective child nodes. Recursive methods are commonly used for this traversal. If any mismatch occurs between nodes or tree structures, the trees are considered different. This method is efficient and straightforward, making it a solid approach to tackle tree comparison problems.

Now, let's go through the same tree problem to understand the comparison of two tree pattern.

Problem Statement

Given the roots of two binary trees, root1 and root2, check if these two binary trees are exactly the same.

Two binary trees are considered the same if they have the same structure and the corresponding nodes hold the same values. If both trees are identical, return true, otherwise, return false.

Examples

Example 1

• Input: root1 = [4, 5, 6, null, 7, 8], root2 = [4, 5, 6, null, 7, 8]

• Expected Output: true
• Justification: Both arrays represent trees with the same structure, and all corresponding values are equal, so the trees are identical.

Example 2:

• Input: root1 = [3, null, 7], root2 = [3, null, 8]

• Expected Output: false
• Justification: Even though the structure is the same, the value at the left child of the root is different (7 in root1, 8 in root2), so the trees are not identical.

We can compare two trees using DFS (Depth-first search) or BFS (Breadth-first search) traversal. Let's learn both approaches.

Using the DFS Approach

The algorithm compares two binary trees using Depth First Search (DFS) by recursively checking if both trees are identical. The process starts at the root nodes of both trees and compares their values. If both nodes are null, the trees are identical at that point. If one node is null and the other is not, the trees are not the same. The algorithm then recursively compares the left and right subtrees. If all corresponding nodes in both trees have the same value and structure, the trees are considered identical; otherwise, they are not.

Step-by-Step Algorithm

1. Check if both trees are null:

   • If root1 and root2 are both null, return true because the trees are identical at this point.

2. Check if one of the trees is null:

   • If one of the trees is null and the other is not, return false because the trees are not the same.

3. Compare node values:

   • If the values of root1.val and root2.val are different, return false because the trees differ at this node.

4. Recursively compare left subtrees:

   • Call the function recursively on root1.left and root2.left. If both left subtrees are identical, continue.

5. Recursively compare right subtrees:

   • Call the function recursively on root1.right and root2.right. If both right subtrees are identical, continue.

6. Return true:

   • If all the above conditions hold true for both left and right subtrees, return true because the trees are identical.

Algorithm Walkthrough

1. Step 1: Compare root nodes:

   • Compare root1.val (4) with root2.val (4).
   • Both are equal, so proceed to the next step.

2. Step 2: Compare left child of root:

   • Compare root1.left.val (5) with root2.left.val (5).
   • Both are equal, so proceed to check their children.

3. Step 3: Compare left child of nodes with value 5:

   • Both root1.left.left and root2.left.left are null, so return true for this subtree.

4. Step 4: Compare right child of nodes with value 5:

   • Compare root1.left.right.val (7) with root2.left.right.val (7).
   • Both are equal, so proceed to check their children.

5. Step 5: Compare left child of nodes with value 7:

   • Both are equal, and both root1.left.right.left and root2.left.right.left are null.
   • This subtree is identical, so return true.

6. Step 6: Compare right child of nodes with value 7:

   • Both root1.left.right.right and root2.left.right.right are null, so return true.

7. Step 7: Compare right child of root:

   • Compare root1.right.val (6) with root2.right.val (6).
   • Both are equal, so proceed to check their children.

8. Step 8: Compare left child of nodes with value 6:

   • Compare root1.right.left.val (8) with root2.right.left.val (8).
   • Both are equal, and both root1.right.left.left and root2.right.left.left are null.
   • This subtree is identical, so return true.

9. Step 9: Compare right child of nodes with value 6:

   • Both root1.right.right and root2.right.right are null, so return true.

10. Final result:

• All nodes and subtrees are identical, so the algorithm returns true, indicating that both trees are identical.

Code

// Definition for a binary tree node
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int x) {
//         val = x;
//     }
// }

public class Solution {

  // DFS function to compare two trees
  public boolean isSameTree(TreeNode root1, TreeNode root2) {
    // If both nodes are null, they are identical at this point
    if (root1 == null && root2 == null) {
      return true;
    }

    // If one of the nodes is null, they are not the same
    if (root1 == null || root2 == null) {
      return false;
    }

    // If values of the current nodes are different, trees are not identical
    if (root1.val != root2.val) {
      return false;
    }

    // Recursively check the left and right subtrees using DFS
    return (
      isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right)
    );
  }

  public static void main(String[] args) {
    // Construct root1: [4, 5, 6, null, 7, 8]
    TreeNode root1 = new TreeNode(4);
    root1.left = new TreeNode(5);
    root1.right = new TreeNode(6);
    root1.left.right = new TreeNode(7);
    root1.right.left = new TreeNode(8);

    // Construct root2: [4, 5, 6, null, 7, 8]
    TreeNode root2 = new TreeNode(4);
    root2.left = new TreeNode(5);
    root2.right = new TreeNode(6);
    root2.left.right = new TreeNode(7);
    root2.right.left = new TreeNode(8);

    // Create solution object
    Solution solution = new Solution();

    // Compare both trees
    boolean result = solution.isSameTree(root1, root2);

    // Print the result
    System.out.println("Are both trees identical? " + result); // Output should be true
  }
}

Complexity Analysis

• Time Complexity: The algorithm visits each node in both trees exactly once, performing constant-time operations (such as value comparison) at each node. Therefore, if n is the number of nodes in each tree, the time complexity is . This complexity applies because, in the worst case, all nodes must be compared.

• Space Complexity: The space complexity depends on the depth of the recursion stack. In the worst case (when the trees are skewed), the depth of recursion can go up to n (the number of nodes), resulting in space complexity. In the best case (balanced trees), the space complexity is due to the recursion stack being proportional to the height of the tree.

Using the BFS Approach

The algorithm uses Breadth First Search (BFS) to check whether two binary trees are identical. It leverages two queues to store nodes from both trees. The algorithm starts by adding the root nodes of both trees to their respective queues. Then, it iteratively processes the nodes level by level. For each node pair, it checks if both nodes are null (skip comparison), if one is null and the other isn't (the trees are different), or if their values differ (the trees are different). If both node values are the same, their left and right children are added to the respective queues for further comparison. The algorithm continues this process until both queues are empty. If both queues are empty at the same time, the trees are identical; otherwise, they are not.

Step-by-Step Algorithm

1. Initialize two queues:

   • Create queue1 for root1 and queue2 for root2.
   • Add root1 to queue1 and root2 to queue2.

2. Loop through both queues (while both queues are not empty):

   • Dequeue node1 from queue1 and node2 from queue2.
   • Check for null nodes:
     • If both node1 and node2 are null, continue to the next iteration.
     • If only one of them is null, return false (trees are not identical).
   • Compare values:
     • If node1.val is not equal to node2.val, return false (trees are different).
   • Add children:
     • Add node1.left and node2.left to their respective queues.
     • Add node1.right and node2.right to their respective queues.

3. Final check:

   • If both queues are empty after the loop, return true (trees are identical).
   • If one queue is still not empty, return false.

Algorithm Walkthrough

Input: root1 = [4, 5, 6, null, 7, 8, null, 9] and root2 = [4, 5, 6, null, 7, 8, null, 9]

1. Step 1: Initialize queue1 and queue2 and add root1 and root2 to them.

   • queue1 = [4], queue2 = [4].

2. Step 2: Dequeue node1 = 4 from queue1 and node2 = 4 from queue2.

   • Compare values: node1.val (4) == node2.val (4), proceed to enqueue children.
   • Enqueue left and right children:
     • queue1 = [5, 6], queue2 = [5, 6].

3. Step 3: Dequeue node1 = 5 from queue1 and node2 = 5 from queue2.

   • Compare values: node1.val (5) == node2.val (5), proceed to enqueue children.
   • node1.left and node2.left are null, so enqueue null for both left children.
   • Enqueue right children:
     • queue1 = [6, null, 7], queue2 = [6, null, 7].

4. Step 4: Dequeue node1 = 6 from queue1 and node2 = 6 from queue2.

   • Compare values: node1.val (6) == node2.val (6), proceed to enqueue children.
   • Enqueue left and right children:
     • queue1 = [null, 7, 8, null], queue2 = [null, 7, 8, null].

5. Step 5: Dequeue node1 = null and node2 = null from both queues.

   • Since both are null, continue to the next iteration.

6. Step 6: Dequeue node1 = 7 from queue1 and node2 = 7 from queue2.

   • Compare values: node1.val (7) == node2.val (7), proceed to enqueue children.
   • Both children are null. Enqeue both children.
     • queue1 = [8, null,null,null], queue2 = [8, null,null,null].

7. Step 7: Dequeue node1 = 8 from queue1 and node2 = 8 from queue2.

   • Compare values: node1.val (8) == node2.val (8), proceed to enqueue children.
     • queue1 = [null,null,null,null,null], queue2 = [null,null,null,null,null].

8. Step 8: Dequeue node1 = null and node2 = null.

   • Both are null, continue.
   • Process all null nodes.

9. Final Step: Both queues are empty, so return true. The trees are identical.

Code

import java.util.LinkedList;
import java.util.Queue;

// Definition for a binary tree node
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int x) {
//         val = x;
//     }
// }

public class Solution {
    // BFS function to compare two trees
    public boolean isSameTree(TreeNode root1, TreeNode root2) {
        // Use a queue to store nodes for level-order traversal
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        
        // Add root nodes of both trees to respective queues
        queue1.offer(root1);
        queue2.offer(root2);
        
        // Loop until both queues are empty
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            
            // If both nodes are null, continue to next iteration
            if (node1 == null && node2 == null) {
                continue;
            }
            
            // If one of the nodes is null, trees are not the same
            if (node1 == null || node2 == null) {
                return false;
            }
            
            // If the node values are different, trees are not identical
            if (node1.val != node2.val) {
                return false;
            }
            
            // Add left and right children of both nodes to respective queues
            queue1.offer(node1.left);
            queue1.offer(node1.right);
            queue2.offer(node2.left);
            queue2.offer(node2.right);
        }
        
        // If both queues are empty at the same time, trees are identical
        return queue1.isEmpty() && queue2.isEmpty();
    }

    public static void main(String[] args) {
        // Construct root1: [4, 5, 6, null, 7, 8]
        TreeNode root1 = new TreeNode(4);
        root1.left = new TreeNode(5);
        root1.right = new TreeNode(6);
        root1.left.right = new TreeNode(7);
        root1.right.left = new TreeNode(8);

        // Construct root2: [4, 5, 6, null, 7, 8]
        TreeNode root2 = new TreeNode(4);
        root2.left = new TreeNode(5);
        root2.right = new TreeNode(6);
        root2.left.right = new TreeNode(7);
        root2.right.left = new TreeNode(8);

        // Create solution object
        Solution solution = new Solution();

        // Compare both trees using BFS
        boolean result = solution.isSameTree(root1, root2);

        // Print the result
        System.out.println("Are both trees identical? " + result); // Output should be true
    }
}

Complexity Analysis

• Time Complexity: The algorithm traverses each node in both trees exactly once. For n nodes in each tree, the time complexity is , as we need to compare every node in both trees.

• Space Complexity: The space complexity depends on the width of the tree. In the worst case (a perfectly balanced tree), the space complexity is due to the queues storing nodes at the current level of the tree.

I just read a lesson on **Introduction to Comparison of Two Trees Pattern** (DSA) and want to truly understand it. Explain Introduction to Comparison of Two Trees Pattern from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Introduction to Comparison of Two Trees Pattern** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Introduction to Comparison of Two Trees Pattern** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Introduction to Comparison of Two Trees Pattern** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.