How do you solve Same Tree on LeetCode?

Same Tree (LeetCode #100) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Both trees must have the same structure and node values to be considered identical.

What is the brute force solution for Same Tree?

The brute force approach for Same Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking each node of both trees recursively. We compare the values and structure of each corresponding node to determine if the trees are identical. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Same Tree?

Same Tree uses the following concepts: Tree, Depth-First Search, Breadth-First Search, Binary Tree. The recommended patterns to study are: Tree Traversal, Recursion.

What are the interview tips for Same Tree?

Always clarify the problem statement and constraints. Discuss your thought process and approach before coding. Consider edge cases, such as empty trees.

What are common mistakes when solving Same Tree?

Not handling null nodes correctly. Assuming trees are the same without checking all nodes.

#100

Same Tree

Easy

TreeDepth-First SearchBreadth-First SearchBinary TreeTree TraversalRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal solution uses a recursive approach to check both trees simultaneously. This allows us to compare nodes in a single pass, improving efficiency.

⚙️

Algorithm

4 steps

1Step 1: If both nodes are null, return true.
2Step 2: If one node is null and the other is not, return false.
3Step 3: If the values of both nodes are different, return false.
4Step 4: Recursively check the left and right children of both nodes.

solution.py8 lines

1def isSameTree(p, q):
2    if not p and not q:
3        return True
4    if not p or not q:
5        return False
6    if p.val != q.val:
7        return False
8    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

ℹ

Complexity note: The time complexity is O(n) because we visit each node once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1Both trees must have the same structure and node values to be considered identical.
2Recursive traversal is a natural fit for tree problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.