Two Sum in BST in DSA Javascript

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 cheapest and most expensive moving inward.

    5
   / \
  3   7
 / \   \
2   4   8

↑ root at 5

Dry Run Walkthrough

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

Goal: Find if two nodes in BST sum to 9

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

Left -> 2, Right -> 8

Why: We check the smallest and largest values first to find the sum efficiently

Step 2: Sum 2 + 8 = 10, which is greater than 9, move right pointer to next smaller (7)

Left -> 2, Right -> 7

Why: Sum too big, so decrease the larger value to get closer to target

Step 3: Sum 2 + 7 = 9, equals target, found the pair

Left -> 2, Right -> 7

Why: Sum matches target, so we found two nodes that add up to 9

Result:

2 -> 7 sum to 9

Annotated Code

DSA Javascript

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

function* inorderTraversal(root) {
  if (!root) return;
  yield* inorderTraversal(root.left);
  yield root.val;
  yield* inorderTraversal(root.right);
}

function* reverseInorderTraversal(root) {
  if (!root) return;
  yield* reverseInorderTraversal(root.right);
  yield root.val;
  yield* reverseInorderTraversal(root.left);
}

function twoSumBST(root, target) {
  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 === target) {
      return [leftVal.value, rightVal.value];
    } else if (sum < target) {
      leftVal = leftIter.next(); // move left pointer forward to increase sum
    } else {
      rightVal = rightIter.next(); // move right pointer backward to decrease sum
    }
  }
  return null;
}

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

const target = 9;
const result = twoSumBST(root, target);
if (result) {
  console.log(`${result[0]} -> ${result[1]} sum to ${target}`);
} else {
  console.log("No pair found");
}

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

initialize pointers to smallest and largest values

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

loop while pointers do not cross

const sum = leftVal.value + rightVal.value;

calculate current sum of two pointers

if (sum === target) { return [leftVal.value, rightVal.value]; }

found pair that sums to target

else if (sum < target) { leftVal = leftIter.next(); }

sum too small, move left pointer forward to increase sum

else { rightVal = rightIter.next(); }

sum too big, move right pointer backward to decrease sum

Output

2 -> 7 sum to 9

Complexity Analysis

Time: O(n) because in worst case we traverse all nodes once with two iterators

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 tree

Returns null immediately, no pairs found

DSA Javascript

if (!root) return;

Single node tree

No pair possible, returns null

DSA Javascript

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

No two nodes sum to target

Returns null after exhausting pointers

DSA Javascript

return null;

When to Use This Pattern

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

Common Mistakes

Mistake: Trying to convert BST to array first without using generators, causing extra space and complexity.
Fix: Use inorder and reverse inorder generators to traverse lazily without extra space.

Mistake: Not checking that left pointer is less than right pointer, causing invalid pairs or infinite loops.
Fix: Add condition leftVal.value < rightVal.value in loop to avoid crossing pointers.

Summary

Finds two nodes in a BST whose values sum to a target number.

Use when you need to check pairs in a BST efficiently without extra space.

The key is using two traversals from smallest and largest values moving inward like two pointers.