Convert Binary Tree of Bakery Orders to Linked List - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-30 mins
  • 🛠️ Topics: Trees, Preorder Traversal, Linked List Conversion

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 bakery order.
  • What operation needs to be performed?
    • The function needs to flatten the binary tree into a 'linked list' using preorder traversal.
  • What should be returned?
    • The function should return the root of the modified tree where all left pointers are None, and right pointers represent the linked list.
HAPPY CASE
Input: 
    items = ["Croissant", "Cupcake", "Bagel", "Cake", "Pie", None, "Blondies"]
Output: 
    ['Croissant', None, 'Cupcake', None, 'Cake', None, 'Pie', None, 'Bagel', None, 'Blondies']
Explanation: 
    The tree structure is flattened to a linked list:
        Croissant
            \
           Cupcake
               \
               Cake
                 \
                 Pie
                   \
                   Bagel
                     \
                    Blondies

EDGE CASE
Input: 
    items = ["Croissant"]
Output: 
    ['Croissant']
Explanation: 
    The tree has only one node, so the linked list is just that node.

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 Tree Flattening problems, we want to consider the following approaches:

  • Preorder Traversal: Preorder traversal is necessary because the linked list needs to maintain the preorder sequence of nodes.
  • In-place Modification: Convert the tree into a linked list in place by manipulating pointers.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • Flatten the left and right subtrees recursively.
  • Attach the left subtree to the right pointer of the current node.
  • Traverse to the end of the new right subtree (which was the left subtree) and attach the original right subtree.
1) Define a recursive function `flatten_orders(node)`:
    - If `node` is `None`, return immediately.
    - Recursively flatten the left and right subtrees.
    - Store the original right subtree.
    - Set the right subtree of the current node to be the flattened left subtree.
    - Set the left pointer of the current node to `None`.
    - Traverse to the end of the new right subtree.
    - Attach the original right subtree to the end of the new right subtree.

⚠️ Common Mistakes

  • Forgetting to set the left pointer to None.
  • Not correctly handling the traversal to the end of the new right subtree.

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 flatten_orders(orders):
    # Base Case: If the node is None, return immediately
    if not orders:
        return
    
    # Flatten the left and right subtrees
    flatten_orders(orders.left)
    flatten_orders(orders.right)
    
    # Store the right subtree
    right_subtree = orders.right
    
    # Place the left subtree as the right subtree
    orders.right = orders.left
    orders.left = None
    
    # Traverse to the end of the new right subtree (originally the left subtree)
    current = orders
    while current.right:
        current = current.right
    
    # Attach the original right subtree
    current.right = right_subtree

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: 
        `items = ["Croissant", "Cupcake", "Bagel", "Cake", "Pie", None, "Blondies"]`
    - Execution: 
        - Flatten the tree into a linked list using preorder traversal.
        - Traverse and adjust the pointers accordingly.
    - Output: 
        ['Croissant', None, 'Cupcake', None, 'Cake', None, 'Pie', None, 'Bagel', None, 'Blondies']

- Example 2:
    - Input: 
        `items = ["Croissant"]`
    - Execution: 
        - Flatten the tree into a linked list.
    - Output: 
        ['Croissant']

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 once during the recursion, and each operation (adjusting pointers) is done in constant time.

Space Complexity:

  • Space Complexity:
    • Balanced Tree: O(H) where H is the height of the tree.
      • Explanation: The recursion stack will have a depth equal to the height of the tree.
    • Unbalanced Tree: O(N) where N is the number of nodes in the tree.
      • Explanation: In the worst case (e.g., a skewed tree), the recursion stack could go as deep as the number of nodes in the tree.