BST Any Greater

TIP101 Unit 8 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Trees, Binary Search Trees, Search Algorithms

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?

• Question: What if the given value is greater than or equal to every node in the tree?
  • Answer: Return False. The function returns True only when some node’s value is strictly greater than value.
• Question: Do we need to visit every node in the tree?
  • Answer: No. In a BST, all values in a node’s left subtree are less than the node’s value, so if the current node isn’t already greater than value we only need to keep searching the right subtree.

HAPPY CASE
Input: TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(8)), TreeNode(15, TreeNode(12), TreeNode(20))), value = 8
Output: True
Explanation: The root value 10 is strictly greater than 8, so the tree contains at least one node whose value is greater than `value`.

EDGE CASE
Input: TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(8)), TreeNode(15, TreeNode(12), TreeNode(20))), value = 25
Output: False
Explanation: The largest value in the tree is 20, which is not greater than 25, so no such node exists.

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.

This is an existence check within a binary search tree (BST). We can exploit the BST invariant — all values in a node’s left subtree are less than the node’s value — to prune the search: once we know the current node is not greater than value, no node in its left subtree can be greater either, so we only ever descend to the right.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Walk down the tree, checking whether each visited node’s value is greater than value. Prune with the BST invariant so at most one path from the root is traversed.

1) Start at the root.
2) If the current node is None, return False.
3) If the current node's value is greater than `value`, return True.
4) Otherwise, every value in the left subtree is <= current node's value <= `value`,
   so recurse only into the right subtree.

⚠️ Common Mistakes

• Using >= instead of >: the function asks for a value strictly greater than value.
• Recursing into both subtrees, which throws away the BST optimization and turns an O(h) search into O(n).
• Forgetting the base case for a None node, causing an AttributeError when the search falls off a branch.

4: I-mplement

Implement the code to solve the algorithm.

def contains_greater_bst(node, value):
    """
    Returns `True` if any node in the binary search tree rooted at `node` has a value greater than `value`.
    Otherwise, returns `False`.
    """

    if node is None:
        return False

    # If the current node's value is greater than `value`, it's a candidate,
    # and we also need to search the left subtree for other candidates.
    if node.val > value:
        return True

    # Since we're searching for a value greater than `value`, explore the right subtree only
    return contains_greater_bst(node.right, value)

5: R-eview

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

• Verify through several examples where values are both present and not present, and both as leaves and non-leaves, to ensure complete accuracy.

6: E-valuate

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

• Time Complexity: O(log n) on average, where n is the number of nodes in the tree. This assumes the tree is balanced, thus the height is about log(n).
• Space Complexity: O(log n) due to the recursion depth, also assuming a balanced tree.