{x}
blog image

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

 

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

 

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -104 <= Node.val <= 104

Solution Explanation:

The problem asks to determine if two given binary trees are structurally identical and have the same node values. Two approaches are presented: Depth-First Search (DFS) and Breadth-First Search (BFS).

Solution 1: Depth-First Search (DFS) - Recursive Approach

This solution employs a recursive DFS approach. The core logic is:

  1. Base Cases:

    • If both p and q are null (empty), they are the same, return true.
    • If one is null and the other isn't, they are different, return false.
    • If their values (p.val and q.val) are different, they are different, return false.

  2. Recursive Step: If the base cases are passed, recursively check if the left subtrees (p.left, q.left) are the same and if the right subtrees (p.right, q.right) are the same. The entire trees are identical only if both recursive calls return true.

Time and Space Complexity Analysis (DFS):

  • Time Complexity: O(min(m, n)), where 'm' and 'n' are the number of nodes in trees 'p' and 'q' respectively. In the worst case, we visit all nodes of the smaller tree.
  • Space Complexity: O(min(m, n)). This is due to the recursive call stack. The maximum depth of the recursion is equal to the height of the smaller tree. In the worst case (a skewed tree), the height can be equal to the number of nodes.

Solution 2: Breadth-First Search (BFS) - Iterative Approach

This solution uses an iterative BFS approach with queues.

  1. Initialization: Create two queues, q1 and q2, and add the root nodes of p and q respectively.

  2. Iteration: While both queues are not empty:

    • Dequeue nodes a and b from q1 and q2.
    • If a.val and b.val differ, return false.
    • Check if the left and right children of a and b are consistently null or not null. If there's an inconsistency, return false.
    • If the left children (a.left and b.left) are not null, enqueue them.
    • If the right children (a.right and b.right) are not null, enqueue them.

  3. Result: If the loop completes without returning false, it means all nodes were compared and the trees are identical; return true.

Time and Space Complexity Analysis (BFS):

  • Time Complexity: O(min(m, n)). Similar to DFS, we visit all nodes of the smaller tree in the worst case.
  • Space Complexity: O(min(m, n)). The maximum size of the queues is bounded by the maximum number of nodes at any level of the smaller tree. In the worst case (a complete binary tree), this can be proportional to the number of nodes.

Both DFS and BFS offer the same time and space complexity for this problem. The choice often depends on personal preference or specific constraints of the input trees. DFS might be slightly more concise in code, while BFS might be preferable when dealing with extremely wide trees where stack overflow could be a concern in a recursive DFS implementation.