Same Tree

Easy

Problem

Return true if two binary trees have the same structure and the same value 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

Test cases

Case 1

Input:    [1,2,3], [1,2,3]
Expected: true

Case 2

Input:    [1,2], [1,null,2]
Expected: false

Case 3

Input:    [1,2,1], [1,1,2]
Expected: false

Case 4

Input:    [], []
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Parallel recursion

Time O(n)Space O(h)

Both empty → same; one empty or values differ → different; else compare children.

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);
}

Subtree of Another Tree reuses this at every node of the larger tree.