Introduction

Comparing two trees is simple only after you define what "same" means. In many problems, two trees are considered equal only if they have the same structure and the same value at every corresponding node. Once that rule is clear, the core algorithm is a recursive walk that compares node pairs in lockstep.

Start with the Equality Definition

Before writing pseudocode, decide whether equality means:

• same shape and same values
• same values even if child order changes
• same leaf sequence only
• same subtree below a chosen node

The standard case is strict equality: both trees must have the same node value in the same position with the same child structure.

Recursive Pseudocode for a Binary Tree

For binary trees, the classic algorithm compares the current nodes, then recurses into left and right children.

1FUNCTION AreEqual(nodeA, nodeB):
2    IF nodeA IS null AND nodeB IS null:
3        RETURN true
4
5    IF nodeA IS null OR nodeB IS null:
6        RETURN false
7
8    IF nodeA.value IS NOT EQUAL TO nodeB.value:
9        RETURN false
10
11    RETURN AreEqual(nodeA.left, nodeB.left)
12       AND AreEqual(nodeA.right, nodeB.right)

This works because every mismatch falls into one of three categories:

1. one node exists where the other does not
2. both nodes exist but their values differ
3. one of the corresponding subtrees differs

Translate the Pseudocode into Real Code

The Python version is almost a direct translation.

1class Node:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8def are_equal(a, b):
9    if a is None and b is None:
10        return True
11    if a is None or b is None:
12        return False
13    if a.value != b.value:
14        return False
15    return are_equal(a.left, b.left) and are_equal(a.right, b.right)
16
17
18t1 = Node(1, Node(2), Node(3))
19t2 = Node(1, Node(2), Node(3))
20print(are_equal(t1, t2))

That is the version to start with unless tree depth is so large that recursion becomes a problem.

Iterative Version with an Explicit Stack

If you want to avoid deep recursion, the same comparison can be written with a stack.

1def are_equal_iterative(a, b):
2    stack = [(a, b)]
3
4    while stack:
5        n1, n2 = stack.pop()
6
7        if n1 is None and n2 is None:
8            continue
9        if n1 is None or n2 is None:
10            return False
11        if n1.value != n2.value:
12            return False
13
14        stack.append((n1.left, n2.left))
15        stack.append((n1.right, n2.right))
16
17    return True

This is logically the same comparison. The only difference is that you manage the traversal state yourself instead of relying on the call stack.

Adapting the Idea to N-ary Trees

If each node has a list of children, compare child counts first, then compare the children pairwise in order.

1FUNCTION AreEqualNary(nodeA, nodeB):
2    IF nodeA IS null AND nodeB IS null:
3        RETURN true
4
5    IF nodeA IS null OR nodeB IS null:
6        RETURN false
7
8    IF nodeA.value IS NOT EQUAL TO nodeB.value:
9        RETURN false
10
11    IF LENGTH(nodeA.children) IS NOT EQUAL TO LENGTH(nodeB.children):
12        RETURN false
13
14    FOR i FROM 0 TO LENGTH(nodeA.children) - 1:
15        IF AreEqualNary(nodeA.children[i], nodeB.children[i]) IS false:
16            RETURN false
17
18    RETURN true

This assumes child order matters. If child order does not matter, the problem is more complex because you need a way to match children independent of position.

Common Pitfalls

The most common mistake is comparing values without comparing structure. Two trees can contain the same values and still be different if the nodes are arranged differently.

Another issue is forgetting the null base cases. The algorithm must handle three possibilities at each position: both nodes missing, only one missing, or both present.

Deep recursion is another concern. A skewed tree can cause recursion depth problems in some languages, so an iterative version may be safer for unbalanced inputs.

Finally, define the equality rule before coding. If one person assumes child order matters and another assumes it does not, both implementations can look reasonable while solving different problems.

Summary

• Tree comparison starts with a precise definition of equality.
• For strict equality, compare null state, node value, and corresponding subtrees.
• Recursive pseudocode is the simplest correct solution for binary trees.
• Use an explicit stack if recursion depth may become an issue.
• For n-ary trees, compare child counts first and then compare children in order.