Unit 8 Session 2 Standard (Click for link to problem statements)
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?
True
if all leaves have the same width, otherwise False
.HAPPY CASE
Input: [7, 7, 7]
Output: True
Explanation: All leaf nodes have the same width.
EDGE CASE
Input: [7, 3, 7]
Output: False
Explanation: The leaf nodes have different widths, so the output is `False`.
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.
For Binary Tree problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Perform a depth-first traversal of the tree to check the width of each leaf node. Compare each leaf's width to the first leaf's width encountered.
1) If the tree is empty, return `True` (since there are no leaves to compare).
2) Initialize a variable `leaf_width` to store the width of the first leaf encountered.
3) Define a helper function `check_leaves(node)` that:
- If the current node is `None`, return `True`.
- If the current node is a leaf (no left or right children):
- If `leaf_width` is `None`, set it to the current node's value.
- Compare the current node's value to `leaf_width`.
- Recursively check the left and right subtrees.
4) Call `check_leaves(root)` and return the result.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.val = value
self.left = left
self.right = right
def same_width(root):
if root is None:
return True
# Variable to store the width of the first leaf encountered
leaf_width = None
def check_leaves(node):
nonlocal leaf_width
if node is None:
return True
# If it's a leaf node
if node.left is None and node.right is None:
if leaf_width is None:
leaf_width = node.val
return node.val == leaf_width
# Recursively check the left and right subtrees
return check_leaves(node.left) and check_leaves(node.right)
return check_leaves(root)
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
- Example 1:
- Input: `snakeplant_1 = TreeNode(7, TreeNode(7), TreeNode(7))`
- Execution:
- Start at root (7).
- Left leaf (7) matches the initial leaf width.
- Right leaf (7) also matches the leaf width.
- Output: `True`
- Example 2:
- Input: `snakeplant_2 = TreeNode(7, TreeNode(3), TreeNode(7))`
- Execution:
- Start at root (7).
- Left leaf (3) does not match the initial leaf width (7).
- Output: `False`
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of nodes in the tree.
O(N)
because each node in the tree is visited exactly once during the traversal.O(H)
where H
is the height of the tree, due to the recursive call stack. In the worst case, this could be O(N)
if the tree is skewed.