Tree Comparison

Structural comparison requires explicit null tracking. DFS naturally enforces this through recursion, while BFS requires careful handling of null positions.

Context

To compare two trees for equality, we must verify two things:

• Structural equality – Nodes exist in the same positions.
• Value equality – Corresponding nodes hold equal values.

Traversal order matters only insofar as it determines whether we correctly preserve structural information during comparison.

A naive BFS implementation that skips null nodes may incorrectly conclude that two trees are equal simply because their level-order values match, even if their structure differs.

Depth-First Search (DFS), especially recursive pre-order comparison, naturally preserves structure because null branches are explicitly checked during recursion.

Core idea

To determine whether two trees are identical:

• If both nodes are null → they match (same structural absence)
• If one is null and the other is not → structure differs → return false
• If values differ → return false
• Otherwise → recursively compare:
  • left subtrees
  • right subtrees

The invariant:

Two trees are equal iff their roots are equal AND their left subtrees are equal AND their right subtrees are equal.

Implementation

public class TreeComparison {
      public static <T> boolean isEqual(BinaryNode<T> a, BinaryNode<T> b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;

        if (!a.getValue().equals(b.getValue())) return false;

        return isEqual(a.getLeft(), b.getLeft())
            && isEqual(a.getRight(), b.getRight());
    }
}