Larger Order Tree - 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 Search Trees, Inorder Traversal, Recursion

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 orders tree is None?
    • Return None since there are no nodes to update.
  • What if the tree has only one node?
    • The node's value will remain unchanged since there are no greater nodes.
  • Is the tree guaranteed to be a binary search tree (BST)?
    • Yes, the problem states that the input tree is a BST.
HAPPY CASE
Input: 
orders = build_tree([4,1,6,0,2,5,7,None,None,None,3,None,None,None,8])
Output: [30,36,21,36,35,26,15,None,None,None,33,None,None,None,8]
Explanation: The tree is traversed in reverse inorder, updating each node's value to include the sum of all greater nodes.

Input: 
orders = build_tree([2,1,3])
Output: [5,6,3]
Explanation: The tree is updated such that each node's value includes the sum of all greater nodes.

EDGE CASE
Input: orders = None
Output: None
Explanation: The tree is empty, so return None.

Input: orders = build_tree([1])
Output: [1]
Explanation: The tree has only one node, so return the node as-is.

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 updating nodes in a binary search tree (BST) based on the values of other nodes, we can consider the following approaches:

  • Reverse Inorder Traversal: Traverse the tree in reverse inorder (right -> node -> left) to accumulate the sum of all greater nodes and update the current node's value.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Base Case:
    • If the orders tree is None, return None.
  2. Reverse Inorder Traversal:
    • Implement a recursive function to perform reverse inorder traversal:
      • Traverse the right subtree first.
      • Update the current node's value to include the cumulative sum of greater nodes.
      • Traverse the left subtree.
  3. Return the root of the updated tree.

Reverse Inorder Traversal Implementation

Pseudocode:

1) Define the base case:
   * If the node is `None`, return the current cumulative sum.

2) Traverse the right subtree.

3) Update the current node's value:
   * Add the cumulative sum to the node's value.
   * Update the cumulative sum to the node's new value.

4) Traverse the left subtree.

5) Return the cumulative sum for use in parent nodes.

4: I-mplement

Implement the code to solve the algorithm.

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

def larger_order_tree(orders):
    def reverse_inorder(node, cumulative_sum):
        if not node:
            return cumulative_sum
        
        # Traverse the right subtree first
        cumulative_sum = reverse_inorder(node.right, cumulative_sum)
        
        # Update the current node's value
        node.val += cumulative_sum
        cumulative_sum = node.val
        
        # Traverse the left subtree
        return reverse_inorder(node.left, cumulative_sum)
    
    reverse_inorder(orders, 0)
    return orders

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 orders = build_tree([4,1,6,0,2,5,7,None,None,None,3,None,None,None,8]):
    • The reverse inorder traversal should correctly update each node's value to include the sum of all greater nodes, resulting in the tree 30,36,21,36,35,26,15,None,None,None,33,None,None,None,8.

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 must be visited once.
  • Space Complexity: O(H) where H is the height of the tree, due to the recursive call stack.