Vertical Bakery Display - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-25 mins
🛠️ Topics: Trees, BFS, Vertical Order 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 a different bakery item.
What operation needs to be performed?
- The function needs to return the vertical order traversal of the tree, organized column by column from left to right.
What should be returned?
- The function should return a list of lists, where each inner list contains the values of the nodes in a specific column.

HAPPY CASE
Input: 
    inventory_items = ["Bread", "Croissant", "Donut", None, None, "Bagel", "Tart"]
Output: 
    ['Croissant'], ['Bread', 'Bagel'], ['Donut'], ['Tart'](/codepath/compsci_guides/wiki/'Croissant'],-['Bread',-'Bagel'],-['Donut'],-['Tart')
Explanation: 
    The tree structure:
         Bread
       /       \
   Croissant    Donut
                /   \
             Bagel Tart
    The vertical order traversal results in four columns: ['Croissant'], ['Bread', 'Bagel'], ['Donut'], ['Tart'](/codepath/compsci_guides/wiki/'Croissant'],-['Bread',-'Bagel'],-['Donut'],-['Tart').

EDGE CASE
Input: 
    inventory_items = []
Output: 
    []
Explanation: 
    The tree is empty, so the output is an empty list.

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 Vertical Order Traversal problems, we want to consider the following approaches:

Breadth-First Search (BFS): BFS is useful for processing nodes level by level and column by column.
Hash Maps: Use a hash map to store lists of nodes grouped by their column indices, allowing efficient grouping and retrieval.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

Use a BFS to traverse the tree while maintaining a column index for each node.
Store nodes in a hash map where the keys are the column indices and the values are lists of nodes at that column.
Once traversal is complete, sort the hash map by column indices and return the values in sorted order.

1) Initialize a dictionary `column_table` to store nodes by their column index.
2) Initialize a queue for BFS that stores pairs `(node, column)` where `column` is the column index of the node.
3) While the queue is not empty:
    - Dequeue the front of the queue.
    - If the node is not `None`, add its value to `column_table[column]`.
    - If the node has a left child, enqueue it with `column - 1`.
    - If the node has a right child, enqueue it with `column + 1`.
4) After BFS completes, sort `column_table` by its keys (column indices).
5) Return a list of lists containing the node values in each column, ordered by column index.

⚠️ Common Mistakes

Forgetting to handle nodes that belong to the same column but are in different rows.
Not correctly maintaining the column indices when adding nodes to the queue.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

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

def vertical_inventory_display(root):
    if not root:
        return []
    
    # Dictionary to hold lists of nodes by their column index
    column_table = {}
    
    # Queue to hold nodes along with their column index
    queue = deque([(root, 0)])
    
    while queue:
        node, column = queue.popleft()
        
        if node:
            # If the column is not already in the dictionary, initialize it with an empty list
            if column not in column_table:
                column_table[column] = []
                
            column_table[column].append(node.val)
            
            # If there is a left child, it goes to column - 1
            queue.append((node.left, column - 1))
            
            # If there is a right child, it goes to column + 1
            queue.append((node.right, column + 1))
    
    # Sort columns and prepare the final output
    sorted_columns = sorted(column_table.keys())
    return [column_table[col] for col in sorted_columns]
    
# Example Usage:
inventory_items = ["Bread", "Croissant", "Donut", None, None, "Bagel", "Tart"]
inventory1 = build_tree(inventory_items)

inventory_items = ["Bread", "Croissant", "Donut", "Muffin", "Scone", "Bagel", "Tart", None, None, "Pie", None, "Cake"]
inventory2 = build_tree(inventory_items)

print(vertical_inventory_display(inventory1))  # ['Croissant'], ['Bread', 'Bagel'], ['Donut'], ['Tart'](/codepath/compsci_guides/wiki/'Croissant'],-['Bread',-'Bagel'],-['Donut'],-['Tart')
print(vertical_inventory_display(inventory2))  # ['Muffin'], ['Croissant', 'Pie'], ['Bread', 'Scone', 'Bagel'], ['Donut', 'Cake'], ['Tart'](/codepath/compsci_guides/wiki/'Muffin'],-['Croissant',-'Pie'],-['Bread',-'Scone',-'Bagel'],-['Donut',-'Cake'],-['Tart')

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: 
        `inventory_items = ["Bread", "Croissant", "Donut", None, None, "Bagel", "Tart"]`
    - Execution: 
        - Perform BFS, group nodes by column index.
        - Sort the columns and prepare the final output.
    - Output: 
        ['Croissant'], ['Bread', 'Bagel'], ['Donut'], ['Tart'](/codepath/compsci_guides/wiki/'Croissant'],-['Bread',-'Bagel'],-['Donut'],-['Tart')

- Example 2:
    - Input: 
        `inventory_items = ["Bread", "Croissant", "Donut", "Muffin", "Scone", "Bagel", "Tart", None, None, "Pie", None, "Cake"]`
    - Execution: 
        - Perform BFS, group nodes by column index.
        - Sort the columns and prepare the final output.
    - Output: 
        ['Muffin'], ['Croissant', 'Pie'], ['Bread', 'Scone', 'Bagel'], ['Donut', 'Cake'], ['Tart'](/codepath/compsci_guides/wiki/'Muffin'],-['Croissant',-'Pie'],-['Bread',-'Scone',-'Bagel'],-['Donut',-'Cake'],-['Tart')

6: E-valuate

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

Time Complexity:

Time Complexity: O(N log N) where N is the number of nodes in the tree.
- Explanation: We visit each node once during BFS, and then sort the column indices, which takes O(N log N).

Space Complexity:

Space Complexity:
- Balanced Tree: O(N) where N is the number of nodes in the tree.
  - Explanation: We store all nodes in the dictionary and the BFS queue.
- Unbalanced Tree: O(N) where N is the number of nodes in the tree.
  - Explanation: Even in the worst case, all nodes are stored in the dictionary and the BFS queue.