Grokking Tree Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Introduction to Comparison of Two Trees Pattern
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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]
Image
  • 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]
Image
  • 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

Image

  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

Python3
Python3
. . . .

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 O(n). 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 O(n) space complexity. In the best case (balanced trees), the space complexity is O(log n) 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]

Image

  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

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: The algorithm traverses each node in both trees exactly once. For n nodes in each tree, the time complexity is O(n), 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 O(n) due to the queues storing nodes at the current level of the tree.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible