Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: p = [1,2,3], q = [1,2,3]
Output: true
Input: p = [1,2], q = [1,null,2]
Output: false
EDGE CASE
Input: p = [], q = []
Output: true
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
If you are dealing with Binary Trees some common techniques you can employ to help you solve the problem:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Recursively traverse both trees using Pre-Order traversal and check if each node is equal to the other.
1. Recursively traverse the tree using Pre-Order traversal
a. If the nodes from both trees are not None, and their values are equal -> Recur on their children
b. Else -> return False
2. After trees have been fully traversed and no differences are discovered, return True
General Idea: Level Order Traversal With Queue and check if each node is equal to the other.
1) Initialize queues used to traverse both trees
2) Push root of respective trees onto the queue, given that they are not None
3) While the queue(s)are not empty:
a) Pop a node from the front of each queue
b) If their values are equal -> Push their children to the end of the queue
c) Else -> return False
4) Once the trees are traversed and no differences are discovered -> return True
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# After trees have been fully traversed and no differences are discovered, return True
if not p and not q:
return True
# If the nodes from both trees are not None, and their values are equal -> Recur on their children
if p and q and p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return False
class Solution:
def isSameTree(self, p, q):
def equalNode(p, q):
# if both are None
if not p and not q:
return True
# one of p and q is None
if not q or not p:
return False
if p.val != q.val:
return False
return True
# Initialize queues used to traverse both trees
deq = deque()
# Push root of respective trees onto the queue, given that they are not None
deq.append((p,q))
# While the queue(s)are not empty
while deq:
# Pop a node from the front of each queue
p, q = deq.popleft()
# If their values are equal -> Push their children to the end of the queue
if equalNode(p, q):
if p and q:
deq.append((p.left, q.left))
deq.append((p.right, q.right))
# Else -> return False
else:
return False
# Once the trees are traversed and no differences are discovered -> return True
return True
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of nodes in binary tree