Same Tree
The key idea
Two trees are the same only if their roots match in value AND their left subtrees are the same AND their right subtrees are the same. Recurse on the two trees in lockstep, comparing the matching nodes; the moment a value differs or one node exists where the other is null, they are not the same.
Problem
You are given the roots of two binary trees p and q. Write a function to check whether the two trees are the same.
Two binary trees are considered the same when they are structurally identical and every pair of matching nodes holds the same value. That means a node that exists in one tree must exist at the very same position in the other, and the two nodes there must carry equal values.
Return true if the trees are the same, and false otherwise.
Constraints
- The number of nodes in both trees is in the range
[0, 100]. -10^4 <= Node.val <= 10^4
Examples
Input: p = [1,2,3], q = [1,2,3]
Output: true
Input: p = [1,2], q = [1,null,2]
Output: false
Input: p = [1,2,1], q = [1,1,2]
Output: false
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY