Introduction to the Same Tree Problem
The "Same Tree" problem is one of the foundational challenges you'll encounter when learning about binary trees and recursion. It appears frequently in coding interviews and on platforms like LeetCode (Problem 100). The task is deceptively simple: given the roots of two binary trees, determine whether they are structurally identical and have the same node values at every corresponding position.
While the problem statement is short, mastering it teaches you essential concepts such as tree traversal, recursive thinking, base case design, and edge case handling. In this tutorial, we'll walk through everything you need to know to solve it confidently in Python.
What Does "Same Tree" Mean?
Two binary trees are considered the same if they satisfy two conditions simultaneously:
- Structural identity: Every node in one tree has a matching node in the other tree at the exact same position.
- Value equality: The values stored in corresponding nodes are equal.
If either the structure differs (for example, one tree has a left child where the other does not) or any pair of corresponding nodes holds different values, the trees are not the same.
Why This Problem Matters
The Same Tree problem matters because it serves as a gateway to more complex tree algorithms. Understanding how to compare two trees recursively builds the mental model you need for problems like subtree checking, tree merging, symmetric tree validation, and even serialization and deserialization of trees.
From an interview perspective, this problem tests several skills at once: your ability to define base cases, your understanding of recursion, your handling of null pointers, and your awareness of time and space complexity. It is often used as a warm-up question before moving on to harder tree problems.
Defining the Tree Node
Before writing any solution, we need a representation of a binary tree node. In Python, this is typically done using a simple class with a value and references to left and right children.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
This definition allows us to construct trees by chaining together TreeNode instances. For example, we can build a small tree with a root value of 1, a left child of 2, and a right child of 3 like this:
# Tree:
# 1
# / \
# 2 3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
Solving Same Tree Recursively
The most natural way to solve this problem is with recursion. The idea is to compare the two roots, then recursively compare their left subtrees and right subtrees. If all three comparisons succeed, the trees are the same.
Designing the Base Cases
Recursion requires clear base cases to terminate correctly. For this problem, there are two important base cases:
- If both nodes are None, they are trivially the same. Return True.
- If only one of the two nodes is None, the structures differ. Return False.
After these checks, we know both nodes exist, so we compare their values and recurse on the children.
The Recursive Implementation
class Solution:
def isSameTree(self, p, q):
# Both nodes are None: structurally identical at this point
if not p and not q:
return True
# Only one node is None: structures differ
if not p or not q:
return False
# Both exist: compare values, then recurse on children
if p.val != q.val:
return False
return (self.isSameTree(p.left, q.left) and
self.isSameTree(p.right, q.right))
Let's trace through an example. Suppose we have two trees that both look like the one we built earlier, with root 1, left child 2, and right child 3. The function first checks that both roots exist and have equal values (1 == 1). It then recurses on the left children (2 == 2) and the right children (3 == 3). Since all comparisons pass and the recursion bottoms out at None nodes, the function returns True.
Testing the Recursive Solution
def build_tree_one():
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
return root
def build_tree_two():
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
return root
def build_tree_three():
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(4) # Different value
return root
solution = Solution()
print(solution.isSameTree(build_tree_one(), build_tree_two())) # True
print(solution.isSameTree(build_tree_one(), build_tree_three())) # False
Solving Same Tree Iteratively
While recursion is elegant, some environments limit recursion depth, and some interviewers prefer an iterative approach. We can solve the same problem using a queue or stack to perform a breadth-first or depth-first traversal of both trees simultaneously.
The iterative approach uses two queues. At each step, we pop one node from each queue and compare them. If they are both None, we continue. If only one is None or their values differ, we return False. Otherwise, we enqueue their children in the same order.
from collections import deque
class Solution:
def isSameTree(self, p, q):
queue_p = deque([p])
queue_q = deque([q])
while queue_p and queue_q:
node_p = queue_p.popleft()
node_q = queue_q.popleft()
# Both None: continue to next pair
if not node_p and not node_q:
continue
# One None, one not: structures differ
if not node_p or not node_q:
return False
# Both exist: compare values
if node_p.val != node_q.val:
return False
# Enqueue children in the same order
queue_p.append(node_p.left)
queue_p.append(node_p.right)
queue_q.append(node_q.left)
queue_q.append(node_q.right)
# Both queues should be empty if trees are the same
return not queue_p and not queue_q
This iterative version produces the same result as the recursive version but avoids the call stack. It is particularly useful when dealing with very deep trees that might cause a recursion limit error in Python.
Complexity Analysis
Both the recursive and iterative solutions visit each node in both trees exactly once. If the trees have n and m nodes respectively, the time complexity is O(min(n, m)) because the algorithm stops as soon as it finds a mismatch.
For the recursive solution, the space complexity is O(min(h1, h2)), where h1 and h2 are the heights of the two trees. This space is used by the call stack. In the worst case of a skewed tree, the height equals the number of nodes, giving O(n) space. For a balanced tree, the height is O(log n).
For the iterative solution, the space complexity is also O(min(n, m)) in the worst case because the queues can hold up to that many nodes at once.
Best Practices
- Always handle None cases first: Checking for None before accessing attributes like val prevents AttributeError exceptions and makes your logic clearer.
- Use short-circuit evaluation: Combining recursive calls with the and operator ensures that if the left subtree comparison fails, the right subtree comparison is skipped, improving efficiency.
- Choose the right approach for the context: Recursion is cleaner and easier to reason about, but iteration is safer for very deep trees. Understand the trade-offs.
- Test edge cases: Always test with two empty trees, one empty and one non-empty tree, trees with a single node, and trees that differ in structure versus value.
- Keep the TreeNode definition consistent: If you are working within a coding platform, use the TreeNode definition provided. In your own projects, document the structure clearly.
Common Pitfalls
One common mistake is forgetting to check the None cases before comparing values. If you write p.val == q.val without first ensuring both nodes exist, your code will crash when one of them is None. Always structure your checks so that None cases are handled first.
Another pitfall is comparing only the values without comparing the structure. For example, checking that both trees contain the same set of values is not enough; the values must appear at the same positions. The recursive and iterative approaches above handle this correctly because they compare children in the same order.
A subtler issue arises when using iterative approaches with stacks instead of queues. If you push children in the wrong order for one tree compared to the other, you can get incorrect results. Always ensure that both trees are traversed in the same order.
Conclusion
The Same Tree problem is a perfect introduction to recursive thinking on binary trees. By carefully defining base cases for None nodes and recursively comparing values and structure, you can solve the problem cleanly and efficiently. Whether you choose the recursive approach for its elegance or the iterative approach for its robustness against deep trees, the key is to handle edge cases explicitly and understand the complexity trade-offs. Mastering this problem lays a strong foundation for tackling more advanced tree algorithms and will serve you well in both interviews and real-world development.