DSA interview question

Check If Two Trees Are Identical

Medium · Data structures · Topics: tree, dfs, recursion

The problem

A configuration service stores settings as binary trees and must decide whether a proposed configuration is exactly the same as the deployed one, meaning the same shape and the same value at every position, before triggering a costly redeploy. Two trees are identical exactly when both are empty, or when both roots have equal values and their left subtrees are identical and their right subtrees are identical. The recursion stops at the first difference.

Example: [1, 2, 3] vs [1, 2, 3] → true; [1, 2] vs [1, null, 2] → false.

Function signature

bool isSameTree(TreeNode* p, TreeNode* q);

Test cases

Input `(p, q)` level order	Output	Explanation
`([1, 2, 3], [1, 2, 3])`	`true`
`([1, 2], [1, null, 2])`	`false`	Same values, different shape
`([1, 2, 1], [1, 1, 2])`	`false`	Children swapped
`([], [])`	`true`	Two empty trees
`([1], [])`	`false`

(Confirm: both structure and values must match; no reordering of children is allowed.)

How interviewers phrase it

"Given the roots of two binary trees p and q, check whether they are the same" (LeetCode 100).

Clarifying questions to ask

Must the structure match, or only the set of values? (The structure too.)
Can children be swapped? (No; that would be "flip equivalent", LeetCode 951.)
Can the trees be empty? (Yes.)

Follow-ups to expect

"What are the base cases?"
"Why can't comparing one traversal work?"
"Iterative version?"
"Mirror check?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview