Two Sum in BST in DSA Typescript

Mental Model

We want to find two numbers in a tree that add up to a target. We use the tree's order to check pairs efficiently.

Analogy: Imagine a sorted list of prices in a store. You want to find two items that together cost exactly your budget. Instead of checking all pairs, you look from the cheapest and the most expensive items moving inward.

      5
     / \
    3   7
   / \   \
  2   4   8

We want to find two nodes whose values add to target.

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, target = 9

Goal: Find if there exist two nodes in BST whose values sum to 9

Step 1: Initialize two pointers: left at smallest (2), right at largest (8)

Left pointer at 2, Right pointer at 8

Why: Start checking pairs from smallest and largest values

Step 2: Sum values: 2 + 8 = 10, which is greater than 9

Sum=10 > target=9, move right pointer to next smaller (7)

Why: Sum too big, decrease sum by moving right pointer left

Step 3: Sum values: 2 + 7 = 9, equals target

Found pair (2,7) that sums to 9

Why: We found two nodes whose values add to target

Result:

2 -> 3 -> 4 -> 5 -> 7 -> 8
Pair found: 2 + 7 = 9

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function* inorderTraversal(root: TreeNode | null): Generator<number> {
  if (!root) return;
  yield* inorderTraversal(root.left);
  yield root.val;
  yield* inorderTraversal(root.right);
}

function* reverseInorderTraversal(root: TreeNode | null): Generator<number> {
  if (!root) return;
  yield* reverseInorderTraversal(root.right);
  yield root.val;
  yield* reverseInorderTraversal(root.left);
}

function findTarget(root: TreeNode | null, k: number): boolean {
  if (!root) return false;

  const leftIter = inorderTraversal(root);
  const rightIter = reverseInorderTraversal(root);

  let leftVal = leftIter.next();
  let rightVal = rightIter.next();

  while (!leftVal.done && !rightVal.done && leftVal.value < rightVal.value) {
    const sum = leftVal.value + rightVal.value;
    if (sum === k) {
      console.log(`Pair found: ${leftVal.value} + ${rightVal.value} = ${k}`);
      return true;
    } else if (sum < k) {
      leftVal = leftIter.next(); // move left pointer forward to increase sum
    } else {
      rightVal = rightIter.next(); // move right pointer backward to decrease sum
    }
  }
  console.log("No pair found");
  return false;
}

// Driver code
const root = new TreeNode(5,
  new TreeNode(3,
    new TreeNode(2),
    new TreeNode(4)
  ),
  new TreeNode(7,
    null,
    new TreeNode(8)
  )
);

console.log("Inorder traversal of BST:");
const inorderValues = [...inorderTraversal(root)];
console.log(inorderValues.join(" -> ") + " -> null");

findTarget(root, 9);

while (!leftVal.done && !rightVal.done && leftVal.value < rightVal.value) {

continue while left pointer is before right pointer to avoid overlap

const sum = leftVal.value + rightVal.value;

calculate sum of current pair values

if (sum === k) {

check if sum matches target

leftVal = leftIter.next(); // move left pointer forward to increase sum

advance left pointer to get larger value when sum too small

rightVal = rightIter.next(); // move right pointer backward to decrease sum

advance right pointer backward to get smaller value when sum too large

Output

Inorder traversal of BST:

2 -> 3 -> 4 -> 5 -> 7 -> 8 -> null

Pair found: 2 + 7 = 9

Complexity Analysis

Time: O(n) because we traverse the BST nodes at most once each from both ends

Space: O(h) where h is tree height due to recursion stack in traversal generators

vs Alternative: Naive approach checks all pairs O(n^2), this uses BST order to reduce to O(n)

Edge Cases

Empty BST

Returns false immediately, no pairs to check

DSA Typescript

if (!root) return false;

BST with one node

No pair possible, returns false

DSA Typescript

while (!leftVal.done && !rightVal.done && leftVal.value < rightVal.value)

No two nodes sum to target

Exhausts pointers without finding pair, returns false

DSA Typescript

console.log("No pair found"); return false;

When to Use This Pattern

When asked to find two numbers summing to a target in a BST, use two-pointer traversal from smallest and largest values to find the pair efficiently.

Common Mistakes

Mistake: Not stopping when left pointer meets or passes right pointer, causing incorrect pairs or infinite loop
Fix: Add condition leftVal.value < rightVal.value in loop to avoid overlap

Mistake: Using normal inorder traversal twice instead of one normal and one reverse inorder
Fix: Use one inorder (smallest to largest) and one reverse inorder (largest to smallest) generator

Summary

Finds if two nodes in a BST sum to a target value using two-pointer traversal.

Use when you need to check pair sums efficiently in a BST without extra space for arrays.

The key insight is to traverse from smallest and largest values simultaneously to find the target sum.