Command Palette

Search for a command to run...

Hectal
Problem 16.3 · Binary TreesEasy

Same Tree

PatternTree DFS

What it teaches: Recurse on two trees at once, comparing structure and values.

Practise it on judges as “Same Tree”.

The problem

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

Constraints

  • 0 ≤ nodes ≤ 100

Pattern clues in the wording

  • → Two trees walked in lockstep

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
p = [1,2,3]
q = [1,2,3]
true
2
p = [1,2]
q = [1,null,2]
false
3
p = [1,2,1]
q = [1,1,2]
false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Recursive comparison · O(n)
1

Recursive comparison

Time O(n) Space O(h)

Check the base cases, then require both left subtrees and both right subtrees to match.

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

Verdict: Stops at the first difference.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Both empty
  • Same values, different shape

Mistakes people make

  • Comparing only values via traversal lists (different shapes can give the same list).

Interview

Follow-up questions

How do you check if one tree is a subtree of another?