Same Tree
LeetCode 100 | Difficulty: Easy
EasyProblem Description
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.
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Constraints:
- The number of nodes in both trees is in the range `[0, 100]`.
- `-10^4 <= Node.val <= 10^4`
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Approach
Tree DFS
Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.
Path problems, subtree properties, tree structure manipulation.
Tree BFS (Level-Order)
Use a queue to process the tree level by level. At each level, process all nodes in the queue, then add their children. Track the level size to know when one level ends and the next begins.
Level-order traversal, level-based aggregation, right/left side view.
Solutions
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| Tree Traversal | $O(n)$ | $O(h)$ |
Interview Tips
- Start by clarifying edge cases: empty input, single element, all duplicates.
- Consider: "What information do I need from each subtree?" — this defines your recursive return value.