โ† Microsoft questions

Check whether two trees are identical

Filed under Microsoft

Free read 3 of 3

Confirm what constitutes equality (both structure and node values must match).

The question

Given the roots of two binary trees `p` and `q`, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Constraints

  • The number of nodes in both trees is in the range [0, 100].
  • -10^4 <= Node.val <= 10^4

Examples

Input
p = [1,2,3], q = [1,2,3]
Output
true
Why
Both trees have the exact same structure and node values.
Input
p = [1,2], q = [1,null,2]
Output
false
Why
Structure differs as the right child is present in one and left in the other.

Approach

  1. Confirm what constitutes equality (both structure and node values must match).

Solution

O(N) time where N is min number of nodes, O(N) space for recursion stack.

Python
class Solution:
    def isSameTree(self, p, q) -> bool:
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Tips

  • What they are testing: Test with empty trees, trees of different heights, and trees with the same values arranged differently.
  • Common mistake: Failing to check for null pointer exceptions when one node is None and the other is not.

Related Microsoft questions

Collected from public candidate posts and coding forums. Updated Nov 2026.