Two Sum in BST in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Sum in BST with target 9

Given the BST below and target = 9, what is the output of the Two Sum function that returns true if two nodes sum to the target?

DSA C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool findTarget(TreeNode* root, int k) {
    std::unordered_set<int> set;
    std::function<bool(TreeNode*)> dfs = [&](TreeNode* node) {
        if (!node) return false;
        if (set.count(k - node->val)) return true;
        set.insert(node->val);
        return dfs(node->left) || dfs(node->right);
    };
    return dfs(root);
}

// BST:
//       5
//      / \
//     3   6
//    / \   \
//   2   4   7

// Call: findTarget(root, 9);

A Compilation error

B false

C true

D Runtime error

💡 Hint

Think about pairs of nodes that add up to 9 in the BST.

The nodes with values 2 and 7 sum to 9, so the function returns true.

❓ Predict Output

intermediate

Output of Two Sum in BST with target 28

Given the BST below and target = 28, what is the output of the Two Sum function that returns true if two nodes sum to the target?

DSA C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool findTarget(TreeNode* root, int k) {
    std::unordered_set<int> set;
    std::function<bool(TreeNode*)> dfs = [&](TreeNode* node) {
        if (!node) return false;
        if (set.count(k - node->val)) return true;
        set.insert(node->val);
        return dfs(node->left) || dfs(node->right);
    };
    return dfs(root);
}

// BST:
//       10
//      /  \
//     5    15
//    / \     \
//   3   7     18

// Call: findTarget(root, 28);

A true

B Compilation error

C false

D Runtime error

💡 Hint

Check if any two nodes sum to 28.

The nodes with values 10 and 18 sum to 28, so the function returns true.

🔧 Debug

advanced

Identify the error in Two Sum BST code

What error does the following Two Sum in BST code produce when run?

DSA C++

bool findTarget(TreeNode* root, int k) {
    std::unordered_set<int> set;
    std::function<bool(TreeNode*)> dfs = [&](TreeNode* node) {
        if (!node) return false;
        if (set.count(k - node->val)) return true;
        set.insert(node->val);
        return dfs(node->left) && dfs(node->right);
    };
    return dfs(root);
}

A Always returns true

B Always returns false

C Stack overflow error

D Correct output

💡 Hint

Look at the logical operator used in recursive calls.

Using && means both left and right must be true to continue, so it stops early and returns false incorrectly.

🧠 Conceptual

advanced

Time complexity of Two Sum in BST using hash set

What is the time complexity of finding if there exist two elements in a BST that sum to a target using a hash set and DFS traversal?

A O(n)

B O(n^2)

C O(log n)

D O(n log n)

💡 Hint

Consider visiting each node once and hash set operations.

Each node is visited once, and hash set lookups and inserts are O(1) on average, so total is O(n).

🚀 Application

expert

Output of Two Sum in BST using two-pointer approach

Given the BST below and target = 16, what is the output of the Two Sum function implemented using two iterators (inorder and reverse inorder) to find if two nodes sum to the target?

DSA C++

#include <stack>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTIterator {
    std::stack<TreeNode*> stk;
    bool reverse;
public:
    BSTIterator(TreeNode* root, bool rev) : reverse(rev) {
        pushAll(root);
    }
    void pushAll(TreeNode* node) {
        while (node) {
            stk.push(node);
            node = reverse ? node->right : node->left;
        }
    }
    int next() {
        TreeNode* tmp = stk.top(); stk.pop();
        if (!reverse) pushAll(tmp->right);
        else pushAll(tmp->left);
        return tmp->val;
    }
    bool hasNext() {
        return !stk.empty();
    }
};

bool findTarget(TreeNode* root, int k) {
    if (!root) return false;
    BSTIterator l(root, false);
    BSTIterator r(root, true);
    int i = l.next();
    int j = r.next();
    while (i < j) {
        if (i + j == k) return true;
        else if (i + j < k) i = l.next();
        else j = r.next();
    }
    return false;
}

// BST:
//       8
//      / \
//     3   10
//    / \    \
//   1   6    14
//      / \   /
//     4   7 13

// Call: findTarget(root, 16);

A Compilation error

B Runtime error

C false

D true

💡 Hint

Check pairs from smallest and largest values moving inward.

Nodes 3 and 13 sum to 16, so the function returns true.