EasyTrees

Same Tree

Check if two trees are same

Solution Approach

Recursively compare node values and subtrees. Both must be null or have same value and structure.

Implementation

def isSameTree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    return (p.val == q.val and 
            isSameTree(p.left, q.left) and 
            isSameTree(p.right, q.right))

Complexity Analysis

Time Complexity

O(min(m,n))

Space Complexity

O(min(h1,h2))

Complexity

Time:O(min(m,n))

Space:O(min(h1,h2))

Asked at

GoogleAmazon