Two Sum in BST in DSA Typescript - Build from Scratch

Two Sum in BST

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find out if there are two numbers in the BST that add up to a specific target value. This is useful in many real-world cases like checking if two prices in a sorted product list sum up to a gift card amount.

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

📋 What You'll Learn

Create a BST with the exact nodes given.

Create a target number variable.

Write a function to find if two numbers in the BST sum to the target.

Print true if such a pair exists, otherwise false.

💡 Why This Matters

🌍 Real World

Finding pairs of numbers that sum to a target is common in finance, shopping discounts, and data analysis where data is stored in sorted structures like BSTs.

💼 Career

Understanding tree traversal and set usage is important for software engineers working with search trees, databases, and optimization problems.

1

Create the BST nodes

Create a class called TreeNode with val, left, and right properties. 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 Typescript

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

Hint

Start by defining the TreeNode class with a constructor. Then create the root node and link its children exactly as described.

2

Set the target sum value

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

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = 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 variable named target and assign it the value 9.

3

Write the function to find two sum in BST

Write a function called findTarget that takes root of type TreeNode | null and k of type number. 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 Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = 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 the function findTarget(root: TreeNode | null, k: number): boolean
// Your code here

Hint

Use a set to remember values you have seen. Traverse the tree with a helper function. For each node, check if the complement (target - node value) is in the set. If yes, return true. Otherwise, add the node value to the set and continue.

4

Print the result of two sum check

Write a console.log statement to print the result of calling findTarget with root and target.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = 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: TreeNode | null, k: number): boolean {
    const seen = new Set();
    function dfs(node: TreeNode | null): boolean {
        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

Call findTarget with root and target, then print the result using console.log.