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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Same Tree

Number: 100

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Meta, Microsoft, Bloomberg, Adobe, tcs, LinkedIn

Problem Description

Given the roots of two binary trees p and q, determine if the two trees are identical. Two binary trees are identical if they are structurally the same and all corresponding nodes have the same value.

Key Insights

  • Use recursion to compare nodes in both trees.
  • If both nodes being compared are null, they are the same.
  • If one node is null while the other is not, the trees differ.
  • Check if current nodes’ values match, then recursively verify the left and right subtrees.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the trees, since every node is visited once. Space Complexity: O(n) in the worst-case (unbalanced tree), due to recursion call stack usage. In a balanced tree, the space would be O(log n).

Solution

The problem can be solved using a recursive approach (Depth-First Search) where we compare the current nodes from both trees. If the current nodes are both null, they match; if one is null, then the trees are not identical. For non-null nodes, check if the values are equal. Then, recursively apply the same logic on the left and right children of the nodes. This approach ensures that both the structure and the node values are identical across the two trees.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def isSameTree(p, q):
    # If both nodes are None, trees are identical at this branch.
    if not p and not q:
        return True
    # If one of the nodes is None, trees are not identical.
    if not p or not q:
        return False
    # Check if current nodes have the same value.
    if p.val != q.val:
        return False
    # Recursively compare the left subtrees and the right subtrees.
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
← Back to All Questions