100. Same Tree
Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search
FAANG asked: 1
Acceptance rate: 54.2%
Problem Breakdown
The problem asks us to determine if two binary trees are the same. Two binary trees are considered the same if they are structurally identical and their corresponding nodes have the same values. The inputs are the roots of two binary trees, p and q. The output is a boolean value: true if the trees are the same, and false otherwise.
Inputs:
- Two binary tree roots,
pandq.
Outputs:
- A boolean indicating whether the two trees are the same.
Implicit Constraints/Edge Cases:
- The trees can be empty.
- Nodes can have negative values.
- The number of nodes in both trees is between 0 and 100.
Intuition
A brute-force approach would involve traversing both trees and comparing each node’s value. However, this could lead to unnecessary comparisons if the structure of the trees differs early on. A more efficient approach involves using a depth-first search (DFS) strategy to traverse both trees simultaneously and compare nodes at each step.
The key insight is that we can recursively check if two trees are the same by ensuring:
- The current nodes have the same value.
- The left subtrees of both nodes are the same.
- The right subtrees of both nodes are the same.
If any of these conditions fail, the trees are not the same.
Approach
We will use a recursive DFS approach to traverse both trees simultaneously. At each step:
- Check if both nodes are
None. If they are, returntruebecause two empty trees are considered the same. - If one node is
Noneand the other is not, returnfalsebecause they cannot be the same. - If the values of the current nodes are different, return
false. - Recursively check if the left subtrees are the same and if the right subtrees are the same.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the smaller tree. We visit each node once.
- Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack, which can go as deep as the height of the tree.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSameTree(p: TreeNode, q: TreeNode) -> bool:
# If both nodes are None, they are the same
if not p and not q:
return True
# If one node is None and the other is not, they are different
if not p or not q:
return False
# Check if current nodes have the same value and recursively check subtrees
return (p.val == q.val) and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
Edge Cases Handled
- Empty Trees: If both trees are empty (
None), they are considered the same. - One Tree Empty, One Not: If one tree is empty and the other is not, they are different.
- Different Values at Current Node: If the values of the current nodes differ, the trees are different.
- Structurally Different Trees: If the structure of the trees differs (e.g., one has a left child where the other does not), they are different.