LESSON 414 OF 536 · BINARY TREES

Same Tree in Java: Recursive Comparison in O(n)

Given the roots of two binary trees, p and q, return true if they are the same tree, and false otherwise.

Two binary trees are the same when they have exactly the same shape and every node holds the same value as the node in the same place in the other tree. Two empty trees are the same.

The trees below are written in level order (top to bottom, left to right), with null for a missing child.

Example 1:

     p          q
     1          1
    / \        / \
   2   3      2   3

Input: p = [1,2,3], q = [1,2,3]
Output: true
Explanation: Both trees have the root 1, with 2 as its left child and 3 as its right child.

Example 2:

     p          q
     1          1
    /            \
   2              2

Input: p = [1,2], q = [1,null,2]
Output: false
Explanation: The trees hold the same values, but the 2 is the left child of the root in p and the right child in q.

Example 3:

     p          q
     1          1
    / \        / \
   2   1      1   2

Input: p = [1,2,1], q = [1,1,2]
Output: false
Explanation: The shapes match, but the left children hold different values: 2 in p and 1 in q.

Constraints:

The number of nodes in each tree is in the range [0, 10⁴].
Each node value is between -10⁴ and 10⁴.
Each tree is at most 400 levels deep.

Note:

Your algorithm should run in O(n) time, where n is the number of nodes, comparing each pair of nodes at most once.

STEP 1 OF 4

Guided

Ctrl + Enter to check

Same Tree in Java, explained

Problem overview

The method isSameTree receives the roots of two binary trees, p and q, and returns true when they are the same tree. Two trees are the same when they have exactly the same shape and every node holds the same value as the node in the same position in the other tree. Two empty trees are the same. The lesson provides the TreeNode class, with an int val, a TreeNode left, a TreeNode right and a constructor TreeNode(int x).

The trees [1, 2, 3] and [1, 2, 3] are the same. The trees [1, 2] and [1, null, 2] hold the same values, but the 2 is a left child in the first and a right child in the second, so they differ. The trees [1, 2, 1] and [1, 1, 2] have the same shape, but their left children hold 2 and 1, so they differ too.

Approach: compare the roots, then the subtrees

Two trees are the same exactly when their roots hold the same value, their left subtrees are the same, and their right subtrees are the same. Each subtree is itself a tree, so the question repeats on smaller trees: recursion fits.

The recursion needs base cases for the places where a tree runs out. Looking at a pair of nodes, one of three things holds:

Both are null. Two empty trees are the same, so the answer is true. This is also where the recursion ends when both sides step past a leaf together.
Exactly one is null. One tree has a node where the other has nothing, so the shapes differ and the answer is false.
Both exist. Compare their values. If they differ, the answer is false. Otherwise the trees are the same exactly when both pairs of subtrees are.

Each pair of nodes is compared at most once, so the algorithm runs in O(n) time, where n is the number of nodes.

Step by step

If both p and q are null, return true. This handles two empty trees and the end of a branch that finishes on both sides at once.
If one of them is null, return false. The first check already took the case of both being empty, so here exactly one is empty and the shapes differ.
If p.val != q.val, return false. Both nodes exist at this point, so reading their values is safe.
Return the two subtree comparisons joined with &&: isSameTree(p.left, q.left) and isSameTree(p.right, q.right). The roots already match, so the trees are the same exactly when both pairs of subtrees are.

The solution in Java

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);
    }
}

Java details worth noticing:

The order of the checks matters. Reading p.val on a null reference throws NullPointerException. A version that compared the values first, called with an empty tree and the tree [1], ended with that exception. The two null checks must come before the value check.
== on references. p == null is the right test for "no node". Comparing p == q would ask whether they are the very same object, which is a different question: two separate trees with equal contents are the same tree for this problem, but not the same object.
int compares with !=. val is a primitive int, so p.val != q.val compares values directly, with no equals needed.
Short-circuit &&. When the left pair already differs, the right pair is not examined.
Recursion depth. Each tree is at most 400 levels deep, which the default Java stack handles easily. Two identical chains of 400 nodes compare as the same, and the same chains with one different node at the bottom compare as different.

Complexity

Time: O(n). Each call looks at one pair of nodes and does constant work, and no pair is visited twice. The recursion stops at the first mismatch, so unequal trees often finish sooner.

Space: O(h), where h is the height of the trees, for the call stack. It is at most 400 here.

Edge cases and common mistakes

Both trees empty. The result is true, from the first check.
One tree empty. An empty tree against [1], in either order, gives false.
Same values, different shape. [1, 2] against [1, null, 2] gives false. Likewise [1, 2, null, 3] against [1, 2, null, null, 3] gives false, because the 3 is a left child in one tree and a right child in the other. Comparing only the sequence of values, without the empty positions, would miss this.
Same shape, different values. [1, 2, 1] against [1, 1, 2] gives false. Checking only the shape is not enough.
Different sizes. [1, 2, 3] against [1, 2] gives false: the right child of the first root has no counterpart.
A single node. [1] against [1] gives true, and [1] against [2] gives false.
Checking only one null. Testing just p == null leaves q.val to fail when q is the empty one.

Testing

[1, 2, 3] and [1, 2, 3] give true.
[1, 2] and [1, null, 2] give false.
[1, 2, 1] and [1, 1, 2] give false.
[] and [] give true.
[] and [1] give false.
[1] and [2] give false.
[1, 2, 3] and [1, 2] give false.
[-10000] and [-10000] give true.

Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free