Two Sum in BST in DSA C++ - Build from Scratch

Two Sum in BST

📖 Scenario: You are working with a phone book stored as a Binary Search Tree (BST). Each node contains a phone number. You want to find if there are two phone numbers in the BST that add up to a specific target sum.

🎯 Goal: Build a program that creates a BST with given phone numbers, sets a target sum, and checks if any two numbers in the BST add up to that target.

📋 What You'll Learn

Create a BST with the exact phone numbers: 10, 5, 15, 3, 7, 18

Create an integer variable called target with the value 22

Implement a function findTarget that returns true if two numbers in the BST add up to target

Print true or false depending on whether such a pair exists

💡 Why This Matters

🌍 Real World

Finding pairs of numbers that add up to a target is useful in financial applications, phone number analysis, and data validation.

💼 Career

Understanding BSTs and hash sets is important for software engineering roles that involve data structures and algorithm optimization.

1

Create the BST with given phone numbers

Create a BST by defining the TreeNode struct and build the tree with these exact phone numbers inserted in this order: 10, 5, 15, 3, 7, 18. Store the root in a variable called root.

DSA C++

// Define TreeNode struct and create BST with root
// Your code here

Hint

Define a TreeNode struct with val, left, and right. Use an insert function to add nodes to the BST.

2

Set the target sum

Create an integer variable called target and set it to 22.

DSA C++

#include 
#include 

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

TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

int main() {
    TreeNode* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 18);

    // Create an integer variable called target and set it to 22
    // Your code here

    return 0;
}

Hint

Just create a variable target and assign it the value 22.

3

Implement the function to find two numbers summing to target

Implement a function called findTarget that takes TreeNode* root and int k as parameters and returns true if there exist two elements in the BST such that their sum is equal to k. Use an unordered_set<int> to store visited values. Call this function inside main.

DSA C++

#include 
#include 

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

TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

bool findTarget(TreeNode* root, int k, std::unordered_set& set) {
    // Your code here
}

int main() {
    TreeNode* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 18);

    int target = 22;

    // Call findTarget and store result
    // Your code here

    return 0;
}

Hint

Use recursion to visit each node. Check if k - root->val is in the set. If yes, return true. Otherwise, add root->val to the set and continue.

4

Print the result

Print the value of the variable result using std::cout. It should print true if two numbers add up to target, otherwise false.

DSA C++

#include 
#include 

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

TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

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

int main() {
    TreeNode* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 18);

    int target = 22;

    std::unordered_set set;
    bool result = findTarget(root, target, set);

    // Print the result
    // Your code here

    return 0;
}

Hint

Use std::cout to print "true" if result is true, otherwise "false".