Bird
Raised Fist0
DSA Cprogramming~5 mins

Two Sum in BST in DSA C - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Two Sum in BST
O(n)
Understanding Time Complexity

We want to know how the time needed grows when finding two numbers in a BST that add up to a target.

How does the search time change as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


// Check if BST has two elements summing to target
bool findTarget(TreeNode* root, int k) {
    unordered_set<int> seen;
    return dfs(root, k, seen);
}

bool dfs(TreeNode* node, int k, unordered_set<int>& seen) {
    if (!node) return false;
    if (seen.count(k - node->val)) return true;
    seen.insert(node->val);
    return dfs(node->left, k, seen) || dfs(node->right, k, seen);
}

This code searches the BST using depth-first search and a set to find if two values sum to the target.

Identify Repeating Operations
  • Primary operation: Visiting each node once in the tree using recursion.
  • How many times: Once per node, so total nodes n times.
How Execution Grows With Input

As the tree grows, the function checks each node once, so the work grows directly with the number of nodes.

Input Size (n)Approx. Operations
10About 10 node visits
100About 100 node visits
1000About 1000 node visits

Pattern observation: The time grows linearly as the tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Because the tree is sorted, we can find the pair in less than linear time without visiting all nodes."

[OK] Correct: Even though the BST is sorted, this method must check nodes to find pairs, so it still visits many nodes in the worst case.

Interview Connect

Understanding how searching a BST for pairs works helps you explain your approach clearly and shows you know how data size affects performance.

Self-Check

"What if we used an in-order traversal with two pointers instead of a set? How would the time complexity change?"

Practice

(1/5)
1. What is the main goal of the Two Sum in BST problem?
easy
A. Check if the BST is balanced.
B. Find the maximum value in the BST.
C. Find two nodes in the BST whose values add up to a given target sum.
D. Count the total number of nodes in the BST.

Solution

  1. Step 1: Understand the problem requirement

    The problem asks to find two nodes in the BST such that their values add up to a target sum.

  2. Step 2: Identify the correct goal

    Among the options, only finding two nodes with values summing to the target matches the problem.

  3. Final Answer:

    Find two nodes in the BST whose values add up to a given target sum. -> Option C

  4. Quick Check:

    Two Sum in BST = Find two nodes summing to target [OK]
Hint: Look for pairs adding to target in BST [OK]
Common Mistakes:
  • Confusing with finding max/min value
  • Thinking it's about counting nodes
  • Assuming it's about tree balance
2. Which of the following is the correct way to declare a function in C that checks for two sum in a BST? 
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
easy
A. void findTwoSum(struct TreeNode root, int target);
B. int findTwoSum(struct TreeNode* root, int* target);
C. int findTwoSum(struct TreeNode root, int target);
D. int findTwoSum(struct TreeNode* root, int target);

Solution

  1. Step 1: Check function parameter types

    The BST root should be passed as a pointer to struct TreeNode, and target as int.

  2. Step 2: Verify return type and parameters

    int findTwoSum(struct TreeNode* root, int target); correctly declares return type int, pointer to root, and int target.

  3. Final Answer:

    int findTwoSum(struct TreeNode* root, int target); -> Option D

  4. Quick Check:

    Function signature with pointer root and int target = int findTwoSum(struct TreeNode* root, int target); [OK]
Hint: Use pointer for tree root in function parameters [OK]
Common Mistakes:
  • Passing struct by value instead of pointer
  • Using void return type when int is needed
  • Passing target as pointer unnecessarily
3. What will be the output of the following code snippet? 

// BST nodes: 5, 3, 6, 2, 4, 7
// Target sum = 9

int main() {
    // Assume createBST() creates the BST with given nodes
    struct TreeNode* root = createBST();
    int target = 9;
    int result = findTwoSum(root, target);
    printf("%d\n", result);
    return 0;
}

// findTwoSum returns 1 if pair found, else 0
medium
A. 1
B. 0
C. Compilation error
D. Runtime error

Solution

  1. Step 1: Identify pairs in BST that sum to target

    Pairs like (2,7) and (3,6) sum to 9 in the BST.

  2. Step 2: Check if findTwoSum returns 1 when pair exists

    Since pairs exist, function returns 1 and prints it.

  3. Final Answer:

    1 -> Option A

  4. Quick Check:

    Pair found = 1 [OK]
Hint: Check if any two nodes sum to target [OK]
Common Mistakes:
  • Assuming no pairs exist
  • Confusing return values
  • Ignoring BST structure
4. Identify the bug in the following code snippet for Two Sum in BST: 

int findTwoSum(struct TreeNode* root, int target) {
    if (!root) return 0;
    int complement = target - root->val;
    if (searchBST(root, complement)) {
        return 1;
    }
    return findTwoSum(root->left, target) || findTwoSum(root->right, target);
}

// searchBST searches for a value in BST
medium
A. It uses wrong target value in recursion.
B. It may count the same node twice as complement.
C. It does not check if root is NULL.
D. It misses checking the left subtree.

Solution

  1. Step 1: Analyze complement calculation and search

    The code searches for complement in the whole tree including current node.

  2. Step 2: Identify issue with counting same node twice

    If complement equals root->val, it may count the same node twice incorrectly.

  3. Final Answer:

    It may count the same node twice as complement. -> Option B

  4. Quick Check:

    Same node counted twice bug = It may count the same node twice as complement. [OK]
Hint: Avoid counting current node as complement [OK]
Common Mistakes:
  • Not excluding current node in search
  • Ignoring NULL checks
  • Wrong recursion parameters
5. Given a BST with nodes [10, 5, 15, 3, 7, 18] and target sum 22, which pair of nodes will the Two Sum in BST algorithm find first if it uses in-order traversal and a hash set to track visited values?
hard
A. (7, 15)
B. (5, 17)
C. (3, 19)
D. (10, 12)

Solution

  1. Step 1: Perform in-order traversal and track visited nodes

    In-order traversal visits nodes in order: 3, 5, 7, 10, 15, 18.

  2. Step 2: Check pairs summing to 22 using hash set

    Process nodes in order: visit 3 (add 3), 5 (add 5), 7 (add 7), 10 (add 10), 15 (complement 7 is in set), so first pair found is (7,15).

  3. Final Answer:

    (7, 15) -> Option A

  4. Quick Check:

    In-order + hash set finds (7,15) first [OK]
Hint: Use in-order + hash set to find pairs fast [OK]
Common Mistakes:
  • Assuming pairs with non-existent nodes
  • Ignoring traversal order
  • Mixing node values incorrectly
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard