Balanced Baked Goods Display - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-25 mins
  • 🛠️ Topics: Trees, Recursion, Height Calculation

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 representing a display of baked goods.
  • What operation needs to be performed?
    • The function needs to determine whether the tree is balanced.
  • What should be returned?
    • The function should return True if the tree is balanced and False otherwise.
HAPPY CASE
Input: 
    baked_goods = ["🎂", "🥮", "🍩", "🥖", "🧁"]
    display1 = build_tree(baked_goods)
Output: 
    True
Explanation: 
    The tree is balanced because the difference in height between the left and right subtrees for every node does not exceed 1.

EDGE CASE
Input: 
    baked_goods = ["🥖", "🧁", "🧁", "🍪", None, None, "🍪", "🥐", None, None, "🥐"]
    display2 = build_tree(baked_goods)
Output: 
    False
Explanation: 
    The tree is not balanced because the height difference between the left and right subtrees at some nodes exceeds 1.

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:

  • Recursion: A recursive approach is natural here to check the balance of subtrees and compute their heights.
  • DFS (Depth-First Search): A DFS traversal can be used to check each node's balance by comparing the heights of its left and right subtrees.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Perform a DFS traversal of the tree to check whether each subtree is balanced. If the subtrees are balanced and the difference in height between them does not exceed 1, the tree is balanced.

1) Define a helper function `check_balance(node)` that:
    - If `node` is `None`, return `True` (balanced) and a height of `0`.
    - Recursively check the balance of the left subtree and calculate its height (`left_balanced`, `left_height`).
    - Recursively check the balance of the right subtree and calculate its height (`right_balanced`, `right_height`).
    - The current node is balanced if both subtrees are balanced and the absolute difference between their heights is less than or equal to `1`.
    - The height of the current node is `max(left_height, right_height) + 1`.
    - Return whether the current node is balanced and its height.

2) In the main `is_balanced` function:
    - Call the `check_balance` function on the root node.
    - Return whether the tree is balanced based on the result from `check_balance`.

⚠️ Common Mistakes

  • Forgetting to return the correct height of a subtree after checking its balance.
  • Not properly handling the base case where the node is None.

4: I-mplement

Implement the code to solve the algorithm.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_balanced(display):
    def check_balance(node):
        if not node:
            return True, 0
        
        left_balanced, left_height = check_balance(node.left)
        right_balanced, right_height = check_balance(node.right)
        
        # Current node is balanced if both subtrees are balanced and their height difference is <= 1
        balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
        
        # Height of the current node is max of left and right subtree heights + 1
        height = max(left_height, right_height) + 1
        
        return balanced, height
    
    balanced, _ = check_balance(display)
    return balanced
    
# Example Usage:
baked_goods = ["🎂", "🥮", "🍩", "🥖", "🧁"]
display1 = build_tree(baked_goods)

baked_goods = ["🥖", "🧁", "🧁", "🍪", None, None, "🍪", "🥐", None, None, "🥐"]
display2 = build_tree(baked_goods)

print(is_balanced(display1))  # True
print(is_balanced(display2))  # False

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: 
        `baked_goods = ["🎂", "🥮", "🍩", "🥖", "🧁"]`
        `display1 = build_tree(baked_goods)`
    - Execution: 
        - Perform DFS to check each node's balance.
        - Heights of left and right subtrees for all nodes are within 1.
    - Output: 
        True

- Example 2:
    - Input: 
        `baked_goods = ["🥖", "🧁", "🧁", "🍪", None, None, "🍪", "🥐", None, None, "🥐"]`
        `display2 = build_tree(baked_goods)`
    - Execution: 
        - Perform DFS to check each node's balance.
        - Height difference exceeds 1 at some nodes.
    - Output: 
        False

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity:

  • Time Complexity: O(N) where N is the number of nodes in the tree.
    • Explanation: Each node is visited exactly once during the DFS traversal to check balance and calculate height.

Space Complexity:

  • Space Complexity: O(H) where H is the height of the tree.
    • Explanation: The recursion stack will use space proportional to the height of the tree. In a balanced tree, H is O(log N), but in the worst case (skewed tree), it could be O(N).