47. Same Tree

EasyBinary Trees & BSTsAlso on LeetCode ↗

Return true if the two binary trees have the same shape and the same values at every node.

Example 1

Input: p = [1,2,3], q = [1,2,3]

Output: true

Example 2

Input: p = [1,2], q = [1,null,2]

Output: false

Hint 1

Compare roots, then recursively compare left with left and right with right.

TreeDFS

Reference solution for Recursion (time O(n), space O(h)). Each solution passes every test in all four languages.

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p or not q:
            return p is q            # both empty -> same; one empty -> different
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) return p == q;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p || !q) return p == q;
        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

function isSameTree(p, q) {
  if (!p || !q) return p === q;
  return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

47. Same Tree

Example 1

Example 2

Approach 1: Recursion ✅