Build confidence with an intuition-first walkthrough focused on tree fundamentals.
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.
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
Example 3:
Input: p = [1,2,1], q = [1,1,2] Output: false
Constraints:
[0, 100].-104 <= Node.val <= 104Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree
[1,2,3] [1,2,3]
[1,2] [1,null,2]
[1,2,1] [1,1,2]
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
if p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn is_same_tree(
p: Option<Rc<RefCell<TreeNode>>>,
q: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
match (p, q) {
(None, None) => true,
(Some(a), Some(b)) => {
let av = a.borrow().val;
let bv = b.borrow().val;
if av != bv {
return false;
}
let al = a.borrow().left.clone();
let ar = a.borrow().right.clone();
let bl = b.borrow().left.clone();
let br = b.borrow().right.clone();
Self::is_same_tree(al, bl) && Self::is_same_tree(ar, br)
}
_ => false,
}
}
}
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (!p && !q) return true;
if (!p || !q) return false;
if (p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Matching values is not enough if one side has missing children.
Usually fails on: Trees with same preorder values but different structure return true incorrectly.
Fix: At each recursion step, compare null-state first, then compare value and recurse both children.
Wrong move: Continuing recursion after a mismatch wastes work and can mask logic bugs.
Usually fails on: First differing node found, but recursion keeps traversing and overwrites result.
Fix: Return false immediately on first mismatch.
Wrong move: Dequeuing one node at a time breaks pairwise alignment between two trees.
Usually fails on: Level-order comparison drifts and compares wrong counterparts.
Fix: Queue node pairs `(pNode, qNode)` and validate them together.