Same Tree

Easy · Trees · Explanation and code example

Breadth First Search

How it works

BFS (level-order traversal) lets us compare the two trees level by level. We maintain two queues—one for each tree. At every step, we remove a pair of nodes that should match:

  • If both nodes are null, they match → continue.
  • If only one is null, or their values differ → trees are not the same.
  • If they match, we push their children into their respective queues in the same order: left child first, then right child.

Steps

  1. Initialize two queues:
    • q1 containing the root of the first tree.
    • q2 containing the root of the second tree.
  2. While both queues are non-empty:
    • Pop one node from each queue: nodeP, nodeQ.
    • If both are null, continue.
    • If only one is null, return false.
    • If their values differ, return false.
    • Enqueue their children:
      • Left children of both trees.
      • Right children of both trees.
  3. After BFS completes with no mismatch, return true.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Incorrect Null Check Order

A common mistake is checking node values before verifying both nodes exist. If one node is null and you access its value, you get a null pointer exception. Always check if both nodes are null first, then if exactly one is null, before comparing values.

Comparing Only Values Without Structure

Some solutions compare just the values using traversals like inorder or preorder, ignoring tree structure. Two trees can have identical traversal sequences but different structures. You must verify both the values and the structural positions match at every node.

Python code example

from typing import Optional
from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        q1 = deque([p])
        q2 = deque([q])

        while q1 and q2:
            for _ in range(len(q1)):
                nodeP = q1.popleft()
                nodeQ = q2.popleft()

                if nodeP is None and nodeQ is None:
                    continue
                if nodeP is None or nodeQ is None or nodeP.val != nodeQ.val:
                    return False

                q1.append(nodeP.left)
                q1.append(nodeP.right)
                q2.append(nodeQ.left)
                q2.append(nodeQ.right)

        return True

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        q1.push(p);
        q2.push(q);

        while (!q1.empty() && !q2.empty()) {
            for (int i = q1.size(); i > 0; i--) {
                TreeNode* nodeP = q1.front(); q1.pop();
                TreeNode* nodeQ = q2.front(); q2.pop();

                if (!nodeP && !nodeQ) continue;
                if (!nodeP || !nodeQ || nodeP->val != nodeQ->val)
                    return false;

                q1.push(nodeP->left);
                q1.push(nodeP->right);
                q2.push(nodeQ->left);
                q2.push(nodeQ->right);
            }
        }

        return true;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations