Course4all
Join us on telegram
Home/dsa/Trees/Same Tree

Same Tree

Master this topic with zero to advance depth.

Same Tree

Given roots of two trees p and q, check if they are the same.

Easy

Examples

Input: p = [1,2,3], q = [1,2,3]
Output: true
Approach 1

Level I: Recursive DFS

Intuition

Two trees are identical if their roots match and their respective subtrees are identical.

Diagram

(1) p.val == q.val? (2) isSameTree(p.left, q.left) (3) isSameTree(p.right, q.right)
⏱ O(N)💾 O(H)

Detailed Dry Run

p(1), q(1) -> match. Recurse(2,2) -> match. Recurse(3,3) -> match. Result = true.

java
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);
    }
}
Approach 2

Level III: Iterative BFS (Parallel Queue)

Intuition

Use a queue to process pairs of nodes from both trees. If any pair differs, trees are not identical.

⏱ O(N)💾 O(W)

Detailed Dry Run

Queue: [(p, q)]. Pop, compare. Push children pairs. Any mismatch -> false.

java
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(p); queue.add(q);
        while (!queue.isEmpty()) {
            TreeNode n1 = queue.poll(), n2 = queue.poll();
            if (n1 == null && n2 == null) continue;
            if (n1 == null || n2 == null || n1.val != n2.val) return false;
            queue.add(n1.left); queue.add(n2.left);
            queue.add(n1.right); queue.add(n2.right);
        }
        return true;
    }
}
← Previous QuestionMaximum Depth of Binary Tree
Next Question →Symmetric Tree