Introduction

Yes. If the goal is to decide whether two binary trees are identical in structure and values, the standard solution is O(n), not O(n log n). In fact, for exact comparison, linear time is also the right lower-bound intuition because in the worst case you may need to inspect every node.

Compare nodes directly with DFS

The direct recursive algorithm compares the current nodes, then compares the left subtrees and right subtrees.

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 same_tree(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 same_tree(a.left, b.left) and same_tree(a.right, b.right)
16
17
18t1 = Node(1, Node(2), Node(3))
19t2 = Node(1, Node(2), Node(3))
20print(same_tree(t1, t2))

Each node pair is checked at most once, so the time complexity is O(n) when both trees contain n nodes and are of similar size. The extra space is the recursion depth, which is O(h) where h is the tree height.

Why O(n log n) is not the right target

O(n log n) often appears in tree problems involving balanced search trees, sorting, or repeated logarithmic searches. Exact tree comparison is different. You do not need to search for nodes; you simply walk the two structures in lockstep.

That is why the problem is easier than the title suggests. Once you already have the two roots, no sorting or lookup structure is required.

Can it be faster than O(n)

In the worst case, not as an exact general solution. Suppose two trees are identical except possibly at the last node you inspect. Any correct algorithm must read enough information to distinguish that case from a completely identical pair.

So while you may return early on mismatches and finish faster on some inputs, the worst-case bound for exact comparison stays linear. That is why O(n) is both practical and essentially optimal here.

Iterative version with a queue

If you want to avoid recursion, use a queue or stack:

1from collections import deque
2
3
4def same_tree_iterative(a, b):
5    queue = deque([(a, b)])
6
7    while queue:
8        left, right = queue.popleft()
9
10        if left is None and right is None:
11            continue
12        if left is None or right is None:
13            return False
14        if left.value != right.value:
15            return False
16
17        queue.append((left.left, right.left))
18        queue.append((left.right, right.right))
19
20    return True

This has the same O(n) time complexity. It just trades recursion for an explicit data structure.

Hashing does not beat the lower bound by itself

People sometimes suggest hashing each tree first and comparing the hashes. That can be useful as a representation trick, but building a correct hash for arbitrary trees still requires visiting the nodes. So hashing can change constants or help with repeated comparisons, but it does not remove the need for linear work in the general exact case.

Common Pitfalls

• Assuming tree comparison must involve searching, sorting, or balancing logic.
• Forgetting that structural equality matters, not just the multiset of values.
• Claiming better-than-linear worst-case time for exact comparison of arbitrary trees.
• Using traversal strings without null markers, which can confuse different structures that share the same values.
• Ignoring recursion depth on very skewed trees when using the recursive version.

Summary

• Exact comparison of two binary trees can be done in O(n) time.
• A simple DFS or BFS that walks both trees together is enough.
• 'O(n log n) is not the natural bound for this problem.'
• In the worst case, exact comparison cannot generally beat linear inspection.
• Choose recursive or iterative traversal based on clarity and tree depth concerns.