We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Same Tree

Difficulty: Easy

Problem Description

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.

Key Insights

  • A recursive approach can be used to traverse both trees simultaneously.
  • At each node, we need to check:
    • If both nodes are null, they are the same.
    • If one node is null and the other is not, they are different.
    • If both nodes are not null, check their values and recursively check their left and right children.
  • The process continues until all nodes are checked or a difference is found.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the trees. We may need to visit each node once. Space Complexity: O(H), where H is the height of the tree due to the recursive call stack.

Solution

The solution involves using a recursive depth-first search (DFS) approach to compare the two trees. At each step, we check the following:

  1. If both nodes are null, return true.
  2. If one node is null while the other is not, return false.
  3. If both nodes are not null, check if their values are the same. If they are, recursively check their left and right children.

This ensures that both the structure and values of the trees are identical.

Code Solutions

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    # Both trees are empty
    if not p and not q:
        return True
    # One tree is empty, the other is not
    if not p or not q:
        return False
    # Check if the current nodes are the same
    if p.val != q.val:
        return False
    # Recursively check left and right subtrees
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
← Back to All Questions