100. Same Tree

← All Problems
easy Trees
Given the roots of two binary trees p and q, determine whether they are structurally identical and have the same node values. Return true if the trees are the same, false otherwise. Both trees can have between 0 and 100 nodes with values in the range [-10,000, 10,000].

Example

Tree p:     1        Tree q:     1
           / \                  / \
          2   3                2   3

Output: true

Both trees have the same structure (root with two children) and identical values at every position: root is 1, left child is 2, right child is 3.

Compare two trees node by node. If both are null, they match. If only one is null or their values differ, they don't match. Otherwise recurse on both left children and both right children — the trees are the same only if every pair matches.

Why this works

Two trees are identical only if every corresponding pair of nodes has the same value and the same structure. By checking three conditions at each step — both null, one null, or values differ — you catch every possible mismatch. Recursion handles the rest by drilling into left and right subtrees simultaneously.

Step by step

  1. Both null — if both nodes are null, this pair matches, return true.
  2. One null — if exactly one node is null, the trees differ in structure, return false.
  3. Compare values — if the values at the current nodes differ, return false.
  4. Recurse on children — check left-left and right-right subtree pairs; both must match.
Time: O(n) Space: O(h) 
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}


class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true; // both empty — they match
        }
        if (p == null || q == null) {
            return false; // structure differs — one is null
        }
        return p.val == q.val &&
               isSameTree(p.left, q.left) &&
               isSameTree(p.right, q.right); // values match, now check subtrees
    }
}

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true; // both empty — they match
        }
        if (!p || !q) {
            return false; // structure differs — one is null
        }
        return p->val == q->val &&
               isSameTree(p->left, q->left) &&
               isSameTree(p->right, q->right); // values match, now check subtrees
    }
};

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def isSameTree(p: TreeNode | None, q: TreeNode | None) -> bool:
    if not p and not q:
        return True  # both empty — they match
    if not p or not q:
        return False  # one is null and the other isn't — mismatch
    return (p.val == q.val and
            isSameTree(p.left, q.left) and
            isSameTree(p.right, q.right))  # values match, now check subtrees