100. Same Tree

Problem Link

To determine whether two binary trees are the same, we compare them node by node, ensuring that both structure and values match exactly and do this recursively for all left and right subtrees. At each pair of nodes, we need to check the following possible cases:

• If both nodes are None, the trees match at this position.
• If both nodes exist, their values must be equal, and their left and right subtrees must also be identical.
• If one node exists and the other does not, the trees differ.

By applying this logic recursively, we ensure that every corresponding node in both trees is checked in the same relative position.

Pseudocode

    function isSameTree(p, q):
    if p is null and q is null:
    return true
    if p is null or q is null:
    return false
    if p.val ≠ q.val:
    return false
    return isSameTree(p.left, q.left) AND isSameTree(p.right, q.right)

Runtime Complexity

Time: O(n) Space: O(h)

PythonGo

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        elif p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    } else if p != nil && q != nil {
        return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
    } else {
        return false
    }
}

---