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.
HAPPY CASE
Input: [2, 3, 5, 6, 7, None, 12]
Output: 3
Explanation: Nodes with odd values are 3, 5, and 7. Hence, 3 leaves have odd splits.
EDGE CASE
Input: None
Output: 0
Explanation: An empty tree should return 0 since there are no leaves to count.
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 Tree problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Traverse the binary tree using recursion and count the number of nodes that have an odd value.
1) If the root is `None`, return `0`.
2) Recursively traverse the left and right subtrees to count the odd splits in each.
3) Check if the current node's value is odd:
- If odd, add 1 to the count from left and right subtrees.
- If even, simply return the sum of counts from left and right subtrees.
4) Return the final count.
⚠️ 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 count_odd_splits(root):
if root is None:
return 0
left_count = count_odd_splits(root.left)
right_count = count_odd_splits(root.right)
# Check if the current node has an odd value
if root.val % 2 != 0:
return 1 + left_count + right_count
else:
return left_count + right_count
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
- Example 1:
- Input: `root = TreeNode(2, TreeNode(3, TreeNode(6), TreeNode(7)), TreeNode(5, None, TreeNode(12)))`
- Execution:
- The root node `2` is even, so we continue to its children.
- The left child `3` is odd, so we count it and move to its children.
- `6` is even, `7` is odd. Add to count.
- The right child `5` is odd, so we count it and move to its child `12`.
- `12` is even.
- Output: `3` (nodes with odd splits are 3, 7, and 5)
- Example 2:
- Input: `root = None`
- Execution: Returns 0 immediately.
- Output: `0`
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 we traverse each node exactly once.O(H)
where H
is the height of the tree, due to the recursive call stack.