Two Sum in BST in DSA Javascript - Build from Scratch

Two Sum in BST

📖 Scenario: You have a phone contact list stored as a Binary Search Tree (BST). Each node contains a contact's phone number. You want to find if there are two contacts whose phone numbers add up to a specific target number.

🎯 Goal: Build a program that checks if there exist two nodes in the BST whose values sum up to a given target number.

📋 What You'll Learn

Create a BST with given nodes

Set a target sum value

Implement a function to find if two numbers in the BST add up to the target

Print true if such a pair exists, otherwise false

💡 Why This Matters

🌍 Real World

Finding pairs of numbers that add up to a target is useful in financial applications, contact management, and data analysis where quick lookups in sorted data structures like BSTs are needed.

💼 Career

This problem helps prepare for coding interviews and real-world tasks involving tree traversal, hashing, and problem-solving with data structures.

1

Create the BST nodes

Create a class called TreeNode with a constructor that takes val, left, and right. Then create the BST with these exact nodes and structure:
root node with value 5,
left child with value 3,
right child with value 6,
left child's left child with value 2,
left child's right child with value 4,
right child's right child with value 7.

DSA Javascript

// Define TreeNode class and create BST nodes as described
// Your code here

Hint

Remember to define the TreeNode class first. Then create the root node with value 5, and add children exactly as described.

2

Set the target sum value

Create a variable called target and set it to the number 9.

DSA Javascript

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

const root = new TreeNode(5,
    new TreeNode(3,
        new TreeNode(2),
        new TreeNode(4)
    ),
    new TreeNode(6,
        null,
        new TreeNode(7)
    )
);

// Create a variable called target and set it to 9
// Your code here

Hint

Just create a constant named target and assign it the value 9.

3

Implement the two sum check function

Write a function called findTarget that takes root and k as parameters. Use a helper Set called seen to store visited node values. Traverse the BST using a helper function dfs. For each node, check if k - node.val is in seen. If yes, return true. Otherwise, add node.val to seen and continue. Return false if no pair found.

DSA Javascript

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

const root = new TreeNode(5,
    new TreeNode(3,
        new TreeNode(2),
        new TreeNode(4)
    ),
    new TreeNode(6,
        null,
        new TreeNode(7)
    )
);

const target = 9;

// Write function findTarget(root, k) using a Set called seen and a helper dfs function
// Your code here

Hint

Use a Set to remember values you have seen. For each node, check if the complement (target - current value) is in the Set. Use recursion to visit all nodes.

4

Print the result

Print the result of calling findTarget with root and target.

DSA Javascript

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

const root = new TreeNode(5,
    new TreeNode(3,
        new TreeNode(2),
        new TreeNode(4)
    ),
    new TreeNode(6,
        null,
        new TreeNode(7)
    )
);

const target = 9;

function findTarget(root, k) {
    const seen = new Set();
    function dfs(node) {
        if (!node) return false;
        if (seen.has(k - node.val)) return true;
        seen.add(node.val);
        return dfs(node.left) || dfs(node.right);
    }
    return dfs(root);
}

// Print the result of findTarget(root, target)
// Your code here

Hint

Use console.log to print the result of findTarget(root, target).