May 30, 2025 • Go • binary tree, depth first search, breadth first search • easy
Problem
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.
Approach
1. Base cases: if both nodes are null (leaves), return true safely. If one node is null and the other isn't there's an imbalance. If the node values aren't equal, they're not the same.
2. After passing all of the base cases, check if the tree's left and right subtree are true/false recursively, ensure both left and right are true at the end.
Reflections
Fairly simple DFS problem in all honesty. One issue I did recognize fairly quickly was that I was using one truthy value for the left and right side, so if right was true it would return true, even when left was false.
Performance
Runtime beats: 100%
Memory beats: 99.4%
Complexity
Time:O(n)
Space:O(n)
Go Solution
func isSameTree(p * TreeNode, q * TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
if p.Val != q.Val {
return false
}
left:= isSameTree(p.Left, q.Left)
right:= isSameTree(p.Right, q.Right)
return left && right
}