Add Row of Cupcakes to Display - codepath/compsci_guides GitHub Wiki

"Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20 mins
  • 🛠️ Topics: Binary Trees, Breadth-First Search, Tree Manipulation

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 should be returned if the depth is 1?
    • Create a new root node with the given flavor and make the original tree the left subtree of this new root.
  • What should happen if the tree is empty?
    • If display is None, return a new tree with a single node having the given flavor.
  • Can the tree have duplicate flavors?
    • Yes, the tree may contain nodes with duplicate flavors.
HAPPY CASE
Input: 
display = build_tree(["Chocolate", "Vanilla", "Strawberry", None, None, "Chocolate", "Red Velvet"])
Output: ['Chocolate', 'Vanilla', 'Strawberry', 'Mocha', 'Mocha', 'Mocha', 'Mocha', None, None, None, None, 'Chocolate', None, None, 'Red Velvet']
Explanation: 
* A row of "Mocha" is added at depth 3. The original subtrees are moved under the newly added nodes.

Input: 
display = build_tree(["Vanilla"])
Output: ['Mocha', 'Vanilla']
Explanation: 
* A new root "Mocha" is created, and "Vanilla" becomes the left subtree.

EDGE CASE
Input: display = None, flavor = "Mocha", depth = 1
Output: ['Mocha']
Explanation: 
* The original tree is empty, so create a new tree with "Mocha" as the root.

Input: display = build_tree(["Vanilla"]), flavor = "Mocha", depth = 2
Output: ['Vanilla', 'Mocha', 'Mocha']
Explanation: 
* The original tree has only one node, so add "Mocha" nodes as the left and right children of "Vanilla".

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 problems involving adding nodes to a binary tree at a specific depth, we can consider the following approaches:

  • Level Order Traversal (BFS): Use a queue to traverse the tree level by level until reaching the desired depth, where the new nodes are added.
  • Tree Manipulation: Carefully rearrange pointers to insert new nodes while preserving the original tree structure.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Base Case:
    • If the depth is 1, create a new root node with the given flavor and set the original tree as its left child. Return the new root.
  2. Level Order Traversal:
    • Implement a BFS to traverse the tree until reaching the level right before the target depth.
    • For each node at this level:
      • Insert new nodes with the given flavor as the left and right children.
      • Reassign the original subtrees to the newly added nodes.
  3. Return the modified tree with the new row of nodes.

BFS Implementation

Pseudocode:

1) If `depth` is `1`, create a new root with the given `flavor` and set the original tree as its left child. Return the new root.

2) Initialize a queue with `display` as the first element and set `current_depth` to 1.

3) While the queue is not empty:
    a) Increment `current_depth` by 1.
    b) Determine the number of nodes at the current level (`level_size = len(queue)`).
    c) For each node at the current level:
       i) Dequeue the node.
       ii) If `current_depth` equals `depth`:
           * Insert new nodes with the given `flavor` as the left and right children.
           * Reassign the original left and right subtrees to the new nodes.
       iii) Otherwise, enqueue the left and right children of the current node for the next level.

4) Return the modified tree.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

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

def add_row(display, flavor, depth):
    if depth == 1:
        new_root = TreeNode(flavor)
        new_root.left = display
        return new_root
    
    queue = deque([display])
    current_depth = 1
    
    while queue:
        current_depth += 1
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.popleft()
            
            # If we are at the depth right before the target depth
            if current_depth == depth:
                old_left = node.left
                old_right = node.right
                
                node.left = TreeNode(flavor)
                node.right = TreeNode(flavor)
                
                node.left.left = old_left
                node.right.right = old_right
            else:
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
    
    return display

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through your code with the input display = build_tree(["Chocolate", "Vanilla", "Strawberry", None, None, "Chocolate", "Red Velvet"]), flavor = "Mocha", depth = 3:
    • The BFS should correctly add a row of "Mocha" nodes at depth 3 and reassign the original subtrees accordingly.

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 may need to be visited to add the new nodes.
  • Space Complexity: O(N) due to the queue storing nodes at each level during traversal.