Two Sum IV in BST

📋

Problem

Imagine you have a sorted collection of numbers stored in a binary search tree, and you want to quickly find if any two numbers add up to a target sum - like finding two friends whose combined ages match a given number.

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to k, otherwise return false.

The number of nodes in the tree is in the range [1, 10^5].-10^4 <= Node.val <= 10^4-10^5 <= k <= 10^5

Edge cases: Single node tree → falseTree with negative values and target sum involving negatives → true/false depending on nodesTarget sum equals twice a node's value but only one such node exists → false

</>

IDE

def findTarget(root: Optional[TreeNode], k: int) -> bool:public boolean findTarget(TreeNode root, int k)bool findTarget(TreeNode* root, int k)function findTarget(root, k)

def findTarget(root: Optional[TreeNode], k: int) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool findTarget(TreeNode* root, int k) {
    // Write your solution here
    return false;
}

function findTarget(root, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: true for single node treeCounting the same node twice as a pair.✅ Ensure pairs consist of two distinct nodes; do not reuse the same node.

Wrong: false when pair exists with negative valuesAssuming all node values are positive and skipping negative sums.✅ Do not assume positivity; check all pairs including negatives.

Wrong: true when no pair sums to kGreedy approach picking largest nodes without checking all pairs.✅ Use hash set or two pointer approach to check all pairs properly.

Wrong: TLE on large inputsUsing O(n^2) brute force nested loops on large BST.✅ Implement O(n) hash set or two pointer approach after inorder traversal.

✓

Test Cases

Handle base cases like empty or single-node trees to avoid runtime errors.

Consider tricky cases that break greedy or incorrect assumptions about node reuse.

Focus on algorithmic efficiency to handle large inputs within time limits.

t1_01basic

Input{"root":[5,3,6,2,4,null,7],"k":9}

Expectedtrue

⏱ Performance - must finish in 2000ms

Nodes with values 2 and 7 sum to 9.

💡 Try an inorder traversal to get sorted node values.

💡 Use two pointers or a hash set to find if two values sum to k.

💡 Check pairs (2,7) or (3,6) to find sum 9.

Why it failed: Failed basic case: likely missed checking all pairs or incorrect traversal. Fix by ensuring inorder traversal and pair sum check.

✓ Correctly identifies pairs summing to k in BST.

t1_02basic

Input{"root":[2,1,3],"k":4}

Expectedtrue

⏱ Performance - must finish in 2000ms

Nodes with values 1 and 3 sum to 4.

💡 Inorder traversal yields sorted array [1,2,3].

💡 Two pointer approach can find sum 4 by checking 1+3.

💡 Return true if any two distinct nodes sum to k.

Why it failed: Failed to find valid pair summing to k; possibly not checking distinct nodes or incorrect sum logic. Fix by verifying pair sums properly.

✓ Correctly finds two nodes summing to k.

t2_01edge

Input{"root":null,"k":5}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty tree has no nodes, so no pairs exist.

💡 Check if root is null before processing.

💡 Return false immediately if tree is empty.

💡 No nodes means no pairs to sum to k.

Why it failed: Did not handle empty tree input; fix by adding null root check returning false.

✓ Correctly returns false for empty tree.

t2_02edge

Input{"root":[1],"k":2}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single node tree cannot form a pair.

💡 Check number of nodes before searching pairs.

💡 Single node means no two distinct nodes exist.

💡 Return false if tree size is less than 2.

Why it failed: Incorrectly returns true for single node; fix by ensuring pairs are distinct nodes.

✓ Correctly returns false for single node tree.

t2_03edge

Input{"root":[1,null,3],"k":2}

Expectedfalse

⏱ Performance - must finish in 2000ms

Target sum equals twice a node's value (1+1=2) but only one node with value 1 exists.

💡 Ensure pairs are distinct nodes, not the same node twice.

💡 Check if two different nodes sum to k, not one node doubled.

💡 Avoid using the same node value twice unless duplicates exist.

Why it failed: Mistakenly uses same node twice for sum; fix by requiring distinct nodes in pair.

✓ Correctly rejects sum from single node used twice.

t3_01corner

Input{"root":[5,3,6,2,4,null,7],"k":28}

Expectedfalse

⏱ Performance - must finish in 2000ms

No two nodes sum to 28; tests greedy approach failure.

💡 Greedy approach picking largest nodes first may fail.

💡 Check all pairs or use hash set to avoid greedy traps.

💡 Verify sums exhaustively or with two pointers.

Why it failed: Greedy approach fails by assuming largest nodes sum to k; fix by checking all pairs or using hash set.

✓ Correctly returns false when no pairs sum to k.

t3_02corner

Input{"root":[1,0,2],"k":2}

Expectedtrue

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack and pair sum; nodes 0 and 2 sum to 2.

💡 This is not a knapsack problem; pairs must be distinct nodes.

💡 Use hash set or two pointer on inorder traversal.

💡 Avoid counting single node multiple times.

Why it failed: Confused with knapsack allowing multiple uses of same node; fix by ensuring pairs are distinct nodes.

✓ Correctly identifies pair summing to k without reuse.

t3_03corner

Input{"root":[0,-2,3,-3,null,2,4],"k":0}

Expectedtrue

⏱ Performance - must finish in 2000ms

Tests handling negative values and zero target; nodes -3 and 3 sum to 0.

💡 BST can have negative values; don't assume all positive.

💡 Hash set or two pointer approach works with negatives.

💡 Check pairs including negative and positive values.

Why it failed: Fails to handle negative values correctly; fix by not assuming all positive and checking all pairs.

✓ Correctly finds pairs summing to zero including negatives.

t4_01performance

Input{"root":[50000,25000,75000,12500,37500,62500,87500,6250,18750,31250,43750,56250,68750,81250,93750,3125,9375,15625,21875,28125,34375,40625,46875,53125,59375,65625,71875,78125,84375,90625,96875,1562,4687,7812,10937,14062,17187,20312,23437,26562,29687,32812,35937,39062,42187,45312,48437,51562,54687,57812,60937,64062,67187,70312,73437,76562,79687,82812,85937,89062,92187,95312,98437,781,2343,3906,5468,7031,8593,10156,11718,13281,14843,16406,17968,19531,21093,22656,24218,25781,27343,28906,30468,32031,33593,35156,36718,38281,39843,41406,42968,44531,46093,47656,49218,50781,52343,53906,55468,57031,58593,60156,61718,63281,64843,66406,67968,69531,71093,72656,74218,75781,77343,78906,80468,82031,83593,85156,86718,88281,89843,91406,92968,94531,96093,97656,99218],"k":100000}

Expectednull

⏱ Performance - must finish in 2000ms

Large BST with 100 nodes, testing O(n) or O(n log n) solutions complete within 2 seconds.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use hash set or two pointer approach for O(n) time.

💡 Inorder traversal plus two pointers or hash set lookup is efficient.

Why it failed: TLE due to O(n^2) brute force approach; fix by using O(n) hash set or two pointer method.

✓ Efficient O(n) or O(n log n) solution passes performance test.

Practice

1. Consider the following code snippet implementing the optimal iterative approach to convert a BST to a Greater Tree. Given the BST with nodes [2, 1, 3], what is the value of the root node after the function completes?

easy

A. 5

B. 6

C. 3

D. 4

Solution

1. Step 1: Trace reverse inorder traversal order

   Nodes visited in order: 3, 2, 1.

2. Step 2: Accumulate sums and update nodes

   acc_sum=0 initially. - Visit 3: acc_sum=3, node.val=3 - Visit 2: acc_sum=3+2=5, node.val=5 - Visit 1: acc_sum=5+1=6, node.val=6 Root node was 2, updated to 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root node value after update is 5 [OK]

Hint: Reverse inorder sums nodes from largest to smallest [OK]

Common Mistakes:

• Confusing traversal order and updating nodes too early
• Off-by-one errors in accumulating sums
• Misidentifying which node is root after updates

2. What is the time complexity of the optimal iterative approach that converts a BST to a Greater Tree using reverse inorder traversal with an explicit stack?

medium

A. O(n) where n is the number of nodes in the BST

B. O(n · h) where n is number of nodes and h is tree height

C. O(n · log n) due to stack operations on balanced BST

D. O(h) where h is the height of the BST because each node is visited once

Solution

1. Step 1: Identify number of nodes visited

   Each node is visited exactly once during traversal.

2. Step 2: Analyze stack operations and overall traversal

   While each node is visited once, the explicit stack can hold up to h nodes, and each push/pop operation can be considered O(1). However, in the worst case (unbalanced tree), the height h can be up to n, making the complexity O(n * h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case complexity depends on tree height [OK]

Hint: Worst-case complexity depends on tree height [OK]

Common Mistakes:

• Assuming stack operations multiply complexity by height unnecessarily
• Confusing recursion stack space with time complexity
• Thinking balanced BST implies O(n log n) time

3. The following code attempts to find the lowest common ancestor in a BST. Identify the bug that causes incorrect results when one node is ancestor of the other.

def lowestCommonAncestor(root, p, q):
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

medium

A. Line 3: Using '<=' and '>=' instead of '<' and '>' causes incorrect ancestor detection.

B. Line 6: Returning current too early without checking if current matches p or q.

C. Line 4: Not handling null root before loop causes crash on empty tree.

D. Line 5: Moving current to left or right without verifying if child exists causes errors.

Solution

1. Step 1: Analyze comparison operators

   Using '<=' and '>=' causes the loop to move past the node when p or q equals current, missing the case where current is ancestor of itself.

2. Step 2: Correct operator usage

   Changing to '<' and '>' ensures the loop stops at the correct ancestor node, including when one node is ancestor of the other.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inclusive comparisons skip valid ancestor nodes [OK]

Hint: Use strict inequalities to detect ancestor nodes correctly [OK]

Common Mistakes:

• Assuming ancestor must be strictly above nodes
• Ignoring null root edge cases
• Returning too early without validation

4. What is the worst-case time complexity of the optimized iterative DFS with BST pruning approach for computing the range sum of a BST with n nodes and height h?

medium

A. O(h) because only nodes along the height are visited

B. O(log n) because pruning skips most nodes

C. O(n) because in worst case pruning does not skip any nodes

D. O(n log n) because each node may be visited multiple times due to stack operations

Solution

1. Step 1: Identify worst-case scenario

   Worst case occurs when all nodes fall within the range or pruning is ineffective, so all n nodes are visited.

2. Step 2: Analyze time complexity

   Each node is processed once, so time complexity is O(n). Stack operations are O(1) amortized per node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Worst case is full traversal, O(n) time [OK]

Hint: Worst case equals full traversal of all nodes [OK]

Common Mistakes:

• Assuming pruning always reduces to O(log n)
• Confusing height h with number of nodes n

5. Suppose the BST can contain negative values and duplicates, and you want to convert it to a Greater Tree where each node's new value is the sum of all nodes with values greater than or equal to it. Which modification to the optimal iterative approach is necessary to handle duplicates correctly?

hard

A. Change traversal to inorder (left-root-right) to process duplicates in ascending order.

B. Use a hash map to store counts of each value and update nodes after traversal.

C. Skip nodes with duplicate values during traversal to avoid double counting.

D. During traversal, accumulate sum including nodes with values equal to current node before updating node value.

Solution

1. Step 1: Understand how duplicates affect sum accumulation

   Duplicates must be included in the sum for nodes with equal values to maintain correctness.

2. Step 2: Modify accumulation logic

   Accumulate sum including all nodes with values >= current node before updating node.val during reverse inorder traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Including equal values in sum ensures correct Greater Tree with duplicates [OK]

Hint: Include equal values in sum during reverse inorder traversal [OK]

Common Mistakes:

• Changing traversal order breaks sum logic
• Skipping duplicates causes incorrect sums
• Using extra data structures unnecessarily increases complexity