Data Structures & Algorithms (Trees): Same Tree

October 21, 2025

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.

same-tree

Solve Here: Leetcode 100

Approach 1: Depth-First Search (DFS)

Binary trees naturally have a recursive structure. Every node in a binary tree can be considered as a root of two smaller binary trees.

The original problem of checking if two binary trees are the same can be broken down into smaller subproblems of checking if the left and right subtrees are the same, provided the values of the current nodes are equal.

intuition

Hypotheses

Let F(p, q) be a function that returns true if the binary trees p and q are the same, otherwise false.

Recursive Steps

// Step 1: Check if the current nodes have the same value
if (p.val == q.val) {
    // Step 2: Recursively check if the left and right subtrees are the same
    return F(q.left, q.left) && F(p.right, q.right);
}

// Step 3: Return false if the current nodes have different values
return false;

Base Conditions

If both trees are empty, they are the same.

if (p == null && q == null) {
    return true;
}

If one of the trees is empty and the other is not, they are not the same.

if(p == null || q == null) {
    return false;
}

Visualization

Tree P123
Tree Q123
ComparingIn stackMatchMismatchnull slot
Algorithm
1boolean isSameTree(TreeNode p, TreeNode q) {
2 if (p == null && q == null) return true;
3 if (p == null || q == null) return false;
4 
5 if (p.val != q.val) return false;
6 
7 if (!isSameTree(p.left, q.left)) return false;
8 return isSameTree(p.right, q.right);
9}
Ready

Press Step or Start to walk through the recursion. Pick a preset below to try a different test case.

Presets
0/16

Time Complexity

Since, we are visting each node in the trees at most once, the overall time complexity = O(min(m, n)), where m and n are the number of nodes in the trees.

Space Complexity

The maximum depth of the recursion stack equals the height of the smaller tree. In case of a balanced tree, the height is log(min(m, n)), however, in the worst case (skewed tree), the height can be min(m, n). Hence, overall space complexity = O(min(m, n)).

Approach 2: Breadth-First Search (BFS)

Use a queue to traverse the trees level by level. At each step, check if the current nodes have the same value. If they do, add their left and right children to the queue. If they don't, return false.

Visualization

Tree P123
Tree Q123
QUEUEempty
ProcessingIn queueMatchMismatchnull slot
Algorithm
1boolean isSameTree(TreeNode p, TreeNode q) {
2 Queue<TreeNode[]> queue = new LinkedList<>();
3 queue.offer(new TreeNode[]{p, q});
4 
5 while (!queue.isEmpty()) {
6 TreeNode[] pair = queue.poll();
7 TreeNode first = pair[0];
8 TreeNode second = pair[1];
9 
10 if (first == null && second == null) continue;
11 if (first == null || second == null) return false;
12 if (first.val != second.val) return false;
13 
14 queue.offer(new TreeNode[]{first.left, second.left});
15 queue.offer(new TreeNode[]{first.right, second.right});
16 }
17 
18 return true;
19}
Ready

Press Step or Start to walk through the BFS. Pick a preset below to try a different test case.

Presets
0/22

Time Complexity

Since, we are visiting each node in the trees at most once, the overall time complexity = O(min(m, n)), where m and n are the number of nodes in the trees.

Space Complexity

The queue grows level by level. At any moment, it holds nodes from a single level of both the trees. So the space complexity depends on the maximum width of the trees.

For a skewed tree, the maximum width is 1. However, in a balanced tree, ith level contains 2^i nodes. For a tree of height h, the maximum width is 2^h = 2^(log(min(m, n))) = min(m, n).

Hence, overall space complexity = O(min(m, n)).