Same Tree

easy
TreesTreeBinary TreeDepth-First Search

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 values.

Examples

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
  • Explanation: The first tree has 2 as its left child, while the second tree has 2 as its right child.

Example 3

  • Input: p = [1,2,1], q = [1,1,2]
  • Output: false

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursive DFS

Intuition

The most natural approach is to compare both trees simultaneously using recursion. At each step, we check whether the current nodes of both trees match -- both null means equal, one null means different, and different values means different. If the current nodes match, we recursively compare their left and right subtrees. Both subtrees must match for the trees to be the same. This divide-and-conquer approach elegantly mirrors the tree structure.

Algorithm

  1. If both p and q are null, return true (both subtrees are empty).
  2. If only one of p or q is null, return false (structural mismatch).
  3. If p.val is not equal to q.val, return false (value mismatch).
  4. Recursively check that the left subtrees are the same AND the right subtrees are the same.
  5. Return the logical AND of both recursive results.
TimeO(n) where n is the minimum number of nodes in either treeSpaceO(h) where h is the height of the tree (O(n) in the worst case)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        if (p == nullptr || q == nullptr) return false;
        if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};
Java 21
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);
    }
}
Python 3.12
def isSameTree(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 isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
Go 1.26
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)
}
Approach 2

Iterative BFS

Intuition

Instead of recursion, we can use an iterative approach with a queue. We enqueue pairs of corresponding nodes from both trees and compare them level by level. For each pair dequeued, we check if they match and then enqueue their corresponding children as pairs. If any pair mismatches, the trees are not the same. This avoids recursion stack overhead and works well for wide, shallow trees.

Algorithm

  1. Push the pair (p, q) onto a queue.
  2. While the queue is not empty, dequeue a pair of nodes.
  3. If both nodes are null, continue to the next pair.
  4. If only one is null or their values differ, return false.
  5. Enqueue the pair (node1.left, node2.left) and the pair (node1.right, node2.right).
  6. If the loop completes without returning false, return true.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<pair<TreeNode*, TreeNode*>> que;
        que.push({p, q});
        while (!que.empty()) {
            auto [n1, n2] = que.front();
            que.pop();
            if (n1 == nullptr && n2 == nullptr) continue;
            if (n1 == nullptr || n2 == nullptr) return false;
            if (n1->val != n2->val) return false;
            que.push({n1->left, n2->left});
            que.push({n1->right, n2->right});
        }
        return true;
    }
};
Java 21
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode[]> queue = new LinkedList<>();
        queue.offer(new TreeNode[] { p, q });
        while (!queue.isEmpty()) {
            TreeNode[] pair = queue.poll();
            TreeNode n1 = pair[0], n2 = pair[1];
            if (n1 == null && n2 == null) continue;
            if (n1 == null || n2 == null) return false;
            if (n1.val != n2.val) return false;
            queue.offer(new TreeNode[] { n1.left, n2.left });
            queue.offer(new TreeNode[] { n1.right, n2.right });
        }
        return true;
    }
}
Python 3.12
from collections import deque


def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    queue = deque([(p, q)])
    while queue:
        n1, n2 = queue.popleft()
        if not n1 and not n2:
            continue
        if not n1 or not n2:
            return False
        if n1.val != n2.val:
            return False
        queue.append((n1.left, n2.left))
        queue.append((n1.right, n2.right))
    return True
Go 1.26
func isSameTree(p *TreeNode, q *TreeNode) bool {
    type pair struct {
        a, b *TreeNode
    }
    queue := []pair{{p, q}}
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        if curr.a == nil && curr.b == nil {
            continue
        }
        if curr.a == nil || curr.b == nil {
            return false
        }
        if curr.a.Val != curr.b.Val {
            return false
        }
        queue = append(queue, pair{curr.a.Left, curr.b.Left})
        queue = append(queue, pair{curr.a.Right, curr.b.Right})
    }
    return true
}

Frequently asked questions

What is the optimal time complexity of Same Tree?

The most efficient approach in this guide ("Iterative BFS") runs in O(n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Same Tree use?

Same Tree is a easy-level Trees problem involving Tree, Binary Tree, Depth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Same Tree be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(h) where h is the height of the tree (O(n) in the worst case), while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
p=
[]
q=
[]
Expected Output
true