Back to solutions

Same Tree

EasyBinary Trees

Return true if two binary trees are structurally identical and have the same node values.

Open problem
Constraints
  • 0 <= nodes <= 100
  • -10^4 <= Node.val <= 10^4

Parallel recursion

Time O(n)Space O(h)

Two trees are equal if both roots are null, or both are non-null with equal values and equal left and right subtrees.

struct TreeNode { int val; TreeNode* left; TreeNode* right; };

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q || p->val != q->val) return false;
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}