☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Check if two trees are identical or not

Medium TUF ID 129 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the roots p and q of two binary trees, return true if the trees are identical: they have exactly the same shape, and every pair of nodes in the same position holds the same value. Two empty trees are identical; an empty tree and a non-empty one are not.

Constraints: up to 100 nodes per tree in the LeetCode version (the methods below are linear, so much larger trees are fine), values fit in an int.

Example 1

p = [1, 2, 3]          q = [1, 2, 3]

    1          1
   / \        / \
  2   3      2   3

answer = true

Example 2

p = [1, 2]             q = [1, null, 2]

    1          1
   /            \
  2              2

answer = false         // same values, but 2 is a left child in p and a right child in q

Example 3

p = [1, 2, 1]          q = [1, 1, 2]

answer = false         // same shape, but the children's values are swapped

Example 2 is the trap. The two trees contain the same values, and even their preorder traversals agree (1, 2 in both). Equality has to capture structure as well as values, and every approach below is a different way of doing that.

Approach 1: Serialize and compare

Intuition. Turn each tree into a sequence that determines the tree uniquely, then compare the sequences. A plain traversal is not enough, as Example 2 shows. But a preorder traversal that writes an explicit marker (here null) for every missing child is unique: reading it back, the marker tells you exactly where each subtree ends, so you can rebuild the tree from it. Two trees are therefore identical if and only if their marked preorder sequences are equal.

For Example 2 the sequences are [1, 2, null, null, null] and [1, null, 2, null, null], which differ at position 1.

Algorithm.

  1. Serialize p into list a and q into list b: at a null node append null; otherwise append the value, then serialize the left child, then the right child.
  2. Return a.equals(b).
static boolean bySerialization(TreeNode p, TreeNode q) {
    List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
    serialize(p, a);
    serialize(q, b);
    return a.equals(b);
}

static void serialize(TreeNode node, List<Integer> out) {
    if (node == null) {
        out.add(null);                 // the marker that pins down the shape
        return;
    }
    out.add(node.val);
    serialize(node.left, out);
    serialize(node.right, out);
}

List.equals compares element by element with Objects.equals, so the null markers are handled safely and Integer values are compared by value, not by reference.

Complexity. Time O(n + m) for the two trees of sizes n and m: both are serialized completely even when they differ at the root. Space O(n + m) for the two lists plus O(h) for the recursion. The idea is valuable beyond this problem: comparing canonical encodings is how subtree matching and serialization problems are attacked.

Approach 2: Optimal, simultaneous recursion

Intuition. Walk both trees at the same time, always standing on the nodes in the same position. At each step there are only three situations:

That is a complete recursive definition of “identical”, so the code is just that definition. The first two cases compress into one line: if either node is null, the trees match exactly when both are, which is p == q.

Algorithm.

  1. If p or q is null, return p == q.
  2. Return p.val == q.val && same(p.left, q.left) && same(p.right, q.right).
static boolean recursive(TreeNode p, TreeNode q) {
    if (p == null || q == null) return p == q;
    return p.val == q.val && recursive(p.left, q.left) && recursive(p.right, q.right);
}

Complexity. Time O(min(n, m)): the walk only visits positions present in both trees, and the && short-circuits at the first difference, so it stops early on mismatch. Space O(h) for the recursion, where h is the smaller height reached.

Dry run on Example 3:

call p node q node result
root 1 1 values equal, check left subtrees
left 2 1 values differ, return false
root     false (the right subtrees are never examined)

Approach 3: Iterative, breadth-first over pairs

Intuition. The same three cases can be checked with a queue instead of recursion, which avoids deep call stacks on degenerate trees. The queue holds pairs of nodes taken from the same position in the two trees. Each pair is checked with the three cases above; if both exist and match, the pair of left children and the pair of right children are added.

Algorithm.

  1. Enqueue the pair (p, q).
  2. While the queue is not empty, dequeue (a, b):
    • if both are null, continue;
    • if exactly one is null or the values differ, return false;
    • otherwise enqueue (a.left, b.left) and (a.right, b.right).
  3. Return true.
static boolean iterative(TreeNode p, TreeNode q) {
    Deque<TreeNode[]> queue = new ArrayDeque<>();
    queue.add(new TreeNode[]{p, q});
    while (!queue.isEmpty()) {
        TreeNode[] pair = queue.poll();
        TreeNode a = pair[0], b = pair[1];
        if (a == null && b == null) continue;
        if (a == null || b == null || a.val != b.val) return false;
        queue.add(new TreeNode[]{a.left, b.left});
        queue.add(new TreeNode[]{a.right, b.right});
    }
    return true;
}

ArrayDeque refuses null elements, but here the elements are two-slot arrays, and an array may contain null entries freely. That is why the pair is stored as TreeNode[] rather than enqueueing the nodes one by one.

Complexity. Time O(min(n, m)), stopping at the first mismatch. Space O(w), where w is the widest level reached.

Edge cases and pitfalls