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. You need to design an iterator over a binary search tree that returns elements in ascending order, but you want to avoid storing all elements upfront to save space. Which approach best fits this requirement?

easy

A. Use a divide-and-conquer approach to merge sorted lists from left and right subtrees at each next() call.

B. Perform a full inorder traversal upfront and store all elements in a list for O(1) next() calls.

C. Use a breadth-first traversal to visit nodes level by level and return elements in sorted order.

D. Use a controlled inorder traversal with a stack to lazily fetch the next smallest element on demand.

Solution

Solution:

1. Step 1: Understand the problem constraints

   The iterator must return elements in ascending order without storing all nodes upfront to save space.

2. Step 2: Evaluate approaches

   Full inorder traversal (B) uses O(n) space upfront, breadth-first (C) does not guarantee sorted order, and divide-and-conquer merging (D) is inefficient per next() call. Controlled inorder traversal with a stack (A) lazily fetches the next smallest element using O(h) space, which is optimal for this problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Lazy stack-based inorder traversal matches the problem requirements [OK]

Hint: Lazy stack traversal avoids full storage [OK]

Common Mistakes:

• Thinking BFS returns sorted order
• Assuming full traversal is always best
• Confusing divide-and-conquer with lazy iteration

2. 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

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

3. The following code attempts to search for a value in a BST. Identify the line containing the subtle bug that can cause incorrect behavior or inefficiency.

def searchBST(root, val):
    if root is None:
        return None
    if root.val == val:
        return root
    left_search = searchBST(root.left, val)
    if left_search is not None:
        return left_search
    return searchBST(root.right, val)

medium

A. Line 5: left_search = searchBST(root.left, val)

B. Line 4: if root.val == val: return root

C. Line 2: if root is None: return None

D. Line 7: return searchBST(root.right, val)

Solution

Solution:

1. Step 1: Understand the code logic

   This code searches both left and right subtrees regardless of BST property.

2. Step 2: Identify inefficiency bug

   Line 5 always searches left subtree even if val > root.val, ignoring BST property and causing O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring BST property causes unnecessary subtree searches [OK]

Hint: Searching both subtrees ignores BST property [OK]

Common Mistakes:

• Not pruning search using BST property

4. What is the time and space complexity of the optimal inorder traversal BST validation algorithm for a tree with n nodes and height h?

medium

A. Time O(n), Space O(h) due to recursion stack where h is tree height

B. Time O(n log n), Space O(n) due to storing all nodes

C. Time O(n^2), Space O(1) because no extra data structures are used

D. Time O(n), Space O(n) because all nodes are stored during traversal

Solution

Solution:

1. Step 1: Identify time complexity

   The algorithm visits each node exactly once in inorder traversal, so time is O(n).

2. Step 2: Identify space complexity

   Space is O(h) due to recursion stack, where h is the height of the tree; no extra arrays store all nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and stack space proportional to tree height [OK]

Hint: Inorder traversal visits each node once, stack depth = tree height [OK]

Common Mistakes:

• Confusing recursion stack space with storing all nodes
• Assuming O(n log n) due to sorting
• Ignoring recursion stack space

5. Suppose you want to extend the BST Iterator to support repeated calls to next() that return the same element multiple times (i.e., allow reuse of elements). Which modification to the Morris traversal based iterator is correct?

hard

A. Remove thread restoration to keep the tree threaded and allow repeated visits to the same node.

B. Store all elements in a list during initialization to allow repeated next() calls without traversal.

C. Modify _advance() to not move current pointer after returning next_val, so next() returns same value again.

D. Use a stack-based iterator and push nodes multiple times to simulate repeated next() calls.

Solution

Solution:

1. Step 1: Understand reuse requirement

   Allowing repeated next() calls to return the same element requires storing elements since Morris traversal advances and loses previous state.

2. Step 2: Evaluate modifications

   Removing thread restoration (A) corrupts tree, modifying _advance() to not move current (C) breaks traversal logic, and pushing nodes multiple times on stack (B) is inefficient and incorrect. Storing all elements upfront (D) enables repeated next() calls reliably.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pre-storing elements supports repeated next() calls without traversal [OK]

Hint: Reuse requires storing elements, not traversal tricks [OK]

Common Mistakes:

• Assuming traversal can be paused and repeated
• Ignoring tree corruption from missing restoration
• Trying to simulate reuse with threads