This content originally appeared on Level Up Coding - Medium and was authored by Abhinav Shukla
Starting with an elegant recursive DFS solution, we’ll explore a BFS approach using level-order traversal, and then discover a creative string serialization technique that transforms the tree comparison problem into a simple string comparison.
Problem Statement
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Constraints:
- The number of nodes in both trees is in the range [0, 100]
- -10⁴ <= Node.val <= 10⁴
Understanding Tree Equality
For two trees to be the same, they must satisfy both conditions:
- Same structure — nodes exist at the same positions
- Same values — corresponding nodes have equal values
Visual Example:
Tree p: Tree q: Same? ✓
1 1
/ \ / \
2 3 2 3
-------------------------
Tree p: Tree q: Same? ✗ (different structure)
1 1
/ \
2 2
-------------------------
Tree p: Tree q: Same? ✗ (different values)
1 1
/ \ / \
2 3 2 4
Key Observation: At each corresponding position, both nodes must either be null together, or both exist with the same value.
Step 1: DFS Recursive Approach
The Idea
Recursively compare nodes at corresponding positions. If both nodes exist and have the same value, recursively check their left and right subtrees.
How it works:
- If both nodes exist:
- Check if values are equal
- Recursively check left subtrees match
- Recursively check right subtrees match
2. If only one node exists (one is null), trees are different
3. If both are null, this position matches
Key Insight: Each node comparison only cares about matching values and delegates subtree checking to recursion!
def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p and q:
if p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return False
elif p or q:
return False
return True
Analysis:
- Time Complexity: O(min(N, M)) — visit nodes until we find a mismatch or finish the smaller tree
- Space Complexity: O(min(N, M)) — recursion stack in worst case (skewed tree)
- Pros: Clean, intuitive recursive solution
- Cons: Uses recursion stack space
- Result: Natural DFS solution following tree structure
Step 2: BFS Level-Order Approach
The Idea
Use a queue to process corresponding nodes from both trees level by level. At each step, verify that the pair of nodes match.
How it works:
- Start with both root nodes in the queue as a pair
- For each pair in the queue:
- If both are null, continue (they match)
- If only one is null or values differ, return False
- Add their left children as a pair to queue
- Add their right children as a pair to queue
3. If we finish processing all pairs without finding mismatches, trees are same
Key Insight: By processing node pairs level by level, we can detect mismatches early without recursion!
from collections import deque
def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
queue = deque([(p, q)])
while queue:
node_p, node_q = queue.popleft()
if not node_p and not node_q:
continue
if not node_p or not node_q or node_p.val != node_q.val:
return False
queue.append((node_p.left, node_q.left))
queue.append((node_p.right, node_q.right))
return True
Analysis:
- Time Complexity: O(N) — each node is visited once, including null children
- Space Complexity: O(N) — in worst case, last level may contain N/2 nodes (half of all nodes)
- Pros: Iterative solution without recursion, early termination on mismatch
- Cons: More code, requires queue data structure
- Result: Clean BFS solution processing pairs level by level
Step 3: String Serialization Approach
The Idea
Convert both trees to string representations using preorder traversal with null markers, then simply compare the strings!
How it works:
- Serialize tree p to a string with preorder traversal (including null markers)
- Serialize tree q to a string the same way
- Compare the two strings — if equal, trees are same!
Visual Flow
Tree p: 1 Tree q: 1
/ \ / \
2 3 2 3
Preorder p: "1|2|null|null|3|null|null"
Preorder q: "1|2|null|null|3|null|null"
Compare: "1|2|null|null|3|null|null" == "1|2|null|null|3|null|null" ✓
Trees are same!
Why preorder/postorder work:
- Preorder: Root first, then complete subtrees — uniquely defines structure and values
- Postorder: Complete subtrees first, then root — also uniquely defines structure and values
Why inorder DOESN’T work:
Tree 1: 2 Tree 2: 2
/ \
2 2
Inorder 1: "null|2|null|2|null"
Inorder 2: "null|2|null|2|null"
Same inorder but DIFFERENT structures! ✗
Inorder doesn’t capture which side (left/right) the child is on!
def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
SEPARATOR = "|"
def preorder(root: Optional[TreeNode]) -> str:
if not root:
return "null" + SEPARATOR
return str(root.val) + SEPARATOR + \
preorder(root.left) + \
preorder(root.right)
p_order = preorder(p)
q_order = preorder(q)
return p_order == q_order
Analysis:
- Time Complexity: O(N) — each node in both trees is visited once
- Space Complexity: O(N) — recursion stack + string storage for both trees
- Pros: Creative approach, shows understanding of tree serialization, can use preorder or postorder
- Cons: More memory for string storage, not as straightforward as direct comparison
- Result: Alternative approach that transforms tree comparison into string comparison
Which approach to use?
- DFS Recursive: Preferred for its simplicity and elegance
- BFS Iterative: When you want to avoid recursion
- String Serialization: Educational value, shows tree representation concepts
This problem beautifully demonstrates multiple ways to solve tree comparison — direct node-by-node comparison (DFS/BFS) or converting trees to strings and comparing representations. The serialization approach teaches an important concept: how tree structure can be captured in a string format!
(LeetCode) Same Tree: 3 Approaches Explained was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Abhinav Shukla
Abhinav Shukla | Sciencx (2025-10-10T16:12:13+00:00) (LeetCode) Same Tree: 3 Approaches Explained. Retrieved from https://www.scien.cx/2025/10/10/leetcode-same-tree-3-approaches-explained/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.