Check if All Leaves in a Snake Plant Have the Same Width - codepath/compsci_guides GitHub Wiki

Unit 8 Session 2 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 15-20 mins
  • 🛠️ Topics: Trees, Binary Trees, Tree Traversal

1: U-nderstand

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?
  • What is the structure of the tree?
    • The tree is a binary tree where each node represents the width of a leaf in a Snake Plant.
  • What operation needs to be performed?
    • The function needs to check if all leaves in the tree have the same width.
  • What should be returned?
    • The function should return 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`.

2: M-atch

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:

  • Tree Traversal: A traversal of the entire tree is needed to check the width of each leaf node.
  • DFS: Depth-First Search can be used to explore all paths from the root to the leaves to ensure all leaves are checked.

3: P-lan

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

  • Not correctly identifying leaf nodes.
  • Failing to account for edge cases, such as a tree with no leaves or only one leaf.

4: I-mplement

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)

5: R-eview

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`

6: E-valuate

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.

  • Time Complexity: O(N) because each node in the tree is visited exactly once during the traversal.
  • Space Complexity: 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.