Check Whether Two Trees Match Exactly

Easy15–20 min

Topics

Binary TreeDFSRecursionSerialization

Companies

AmazonGoogleMicrosoftApple

You are given the roots of two binary trees. Decide whether they are exactly the same: they must have the same shape, and each pair of corresponding nodes must hold the same value. Two empty trees are considered the same.

Comparing the trees node by node is the direct approach. A tempting shortcut — comparing only the list of values — is wrong, because the same values can be arranged in different shapes.

Test Case 1:

Input:a = [7, 3, 9, 1], b = [7, 3, 9, null, 1]

Output:false

Explanation:Both trees hold the same values, but in a, node 1 hangs on the LEFT of node 3, while in b it hangs on the RIGHT. Same values in a different arrangement do not match.

Test Case 2:

Input:a = [5, 2, 8], b = [5, 2, 8]

Output:true

Explanation:Same shape, same values at every position.

Test Case 3:

Input:a = [], b = []

Output:true

Explanation:Two empty trees match.

Constraints

◆0 ≤ number of nodes in each tree ≤ 100
◆−1000 ≤ node.val ≤ 1000
◆Each tree is given by its root node (null for an empty tree); each node has a val, a left child and a right child
◆Two trees match when they have the same shape AND every pair of corresponding nodes holds the same value. Return true if they match, false otherwise

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Encode Both Trees and Compare the Strings

Brute

Turn each tree into a string that records its whole structure: a missing child becomes "#", and a node becomes its value followed by the encoding of its left subtree and then of its right subtree, separated by commas. The "#" markers are essential — they make the shape part of the string, so [7, 3, 9, 1] and [7, 3, 9, null, 1] (same values, node 1 on the other side) encode differently. The trees match exactly when the two strings are equal. It is correct but builds two strings of length proportional to the trees, so it always spends O(n + m) time and space, even when the trees differ at the very first node.

TimeO(n + m)

SpaceO(n + m)

Java

Try it out

class Solution {
    public boolean treesMatch(TreeNode a, TreeNode b) {
        return encode(a).equals(encode(b));
    }

    private String encode(TreeNode node) {
        if (node == null) return "#";
        return node.val + "," + encode(node.left) + "," + encode(node.right);
    }
}

Optimal — Compare Node by Node and Stop at the First Difference

Optimal

Walk both trees in lock-step. If both current nodes are missing, this spot matches. If only one is missing, the shapes differ — return false. If both exist but hold different values, return false. Otherwise the two nodes match, and the trees match only if the left subtrees match AND the right subtrees match. The "&&" short-circuits: the first difference ends the whole comparison at once, and no strings are built. The work is bounded by the smaller tree, and the extra space is just the recursion depth, O(h).

TimeO(min(n, m))

SpaceO(h)