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.

Practice

1. What is the main goal of the Two Sum in BST problem?

easy

A. Check if a BST is balanced

B. Find two nodes in a BST whose values add up to a target sum

C. Count the number of nodes in a BST

D. Find the maximum value in a BST

Solution

1. Step 1: Understand the problem statement

   The problem asks to find two nodes in a Binary Search Tree (BST) such that their values add up to a given target sum.

2. Step 2: Identify the goal

   The goal is to check if such a pair exists, not to find maximum, count nodes, or check balance.

3. Final Answer:

   Find two nodes in a BST whose values add up to a target sum -> Option B

4. Quick Check:

   Two Sum in BST = Find pair with target sum [OK]

Hint: Look for two values adding to target in BST [OK]

Common Mistakes:

• Confusing with finding max or min value
• Thinking it counts nodes instead of finding pairs
• Assuming it checks tree balance

2. Which TypeScript syntax correctly defines a BST node for the Two Sum problem?

easy

A. interface TreeNode { val: string; left: TreeNode; right: TreeNode; }

B. function TreeNode(val) { this.val = val; this.left = null; this.right = null; }

C. type TreeNode = { val: number; left?: TreeNode; right?: TreeNode; }

D. class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } }

Solution

1. Step 1: Check correct TypeScript class syntax for BST node

   class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } } defines a class with number value and nullable left/right children, matching BST node structure.

2. Step 2: Compare other options

   function TreeNode(val) { this.val = val; this.left = null; this.right = null; } is JavaScript function style, not TypeScript class. interface TreeNode { val: string; left: TreeNode; right: TreeNode; } uses string type for val and non-nullable children, which is incorrect. type TreeNode = { val: number; left?: TreeNode; right?: TreeNode; } uses optional properties but lacks constructor and proper null handling.

3. Final Answer:

   class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } } -> Option D

4. Quick Check:

   Correct BST node class syntax = class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } } [OK]

Hint: Use class with nullable left/right and number val [OK]

Common Mistakes:

• Using string type for node value
• Not initializing left and right to null
• Using JavaScript function instead of TypeScript class

3. Given the BST below and target = 9, what will the Two Sum function return?

    5
   / \
  3   7
 /     \
2       8

Function uses in-order traversal and a set to find pairs.

medium

A. true

B. false

C. null

D. Error

Solution

1. Step 1: Traverse BST in-order and check pairs

   In-order traversal gives sorted values: [2, 3, 5, 7, 8]. We check if target - current value exists in set.

2. Step 2: Find pair summing to 9

   Check pairs: 2 + 7 = 9 (found), so function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   2 + 7 = 9 found in BST [OK]

Hint: In-order traversal gives sorted list to find pairs [OK]

Common Mistakes:

• Assuming no pair without checking all nodes
• Confusing traversal order
• Ignoring set lookup for complements

4. Identify the bug in this TypeScript Two Sum in BST function snippet:

function findTarget(root: TreeNode | null, k: number): boolean {
  const set = new Set<number>();
  function dfs(node: TreeNode | null): boolean {
    if (!node) return false;
    if (set.has(k - node.val)) return true;
    set.add(node.val);
    dfs(node.left);
    dfs(node.right);
    return false;
  }
  return dfs(root);
}

medium

A. The base case should return true when node is null

B. Set is not initialized properly

C. The function returns false too early, missing true from recursive calls

D. The function should use a queue instead of recursion

Solution

1. Step 1: Analyze recursive calls and return values

   The dfs function calls dfs(node.left) and dfs(node.right) but ignores their return values, always returning false at the end.

2. Step 2: Identify missing return propagation

   If dfs(node.left) or dfs(node.right) returns true, dfs should return true immediately to propagate the success.

3. Final Answer:

   The function returns false too early, missing true from recursive calls -> Option C

4. Quick Check:

   Return recursive true results to avoid missing pairs [OK]

Hint: Return recursive calls' results to propagate true [OK]

Common Mistakes:

• Ignoring return values of recursive calls
• Returning false before checking all nodes
• Misunderstanding base case return

5. You want to optimize Two Sum in BST for large trees. Which approach best reduces time complexity while using O(h) space, where h is tree height?

hard

A. Use two pointers with iterative in-order and reverse in-order traversals simultaneously

B. Convert BST to array and use nested loops to find pairs

C. Use breadth-first search with a hash set to find pairs

D. Perform recursive DFS and store all node values in a list before checking pairs

Solution

1. Step 1: Understand space and time constraints

   We want to reduce time complexity and keep space to O(h), where h is tree height.

2. Step 2: Evaluate approaches

   Use two pointers with iterative in-order and reverse in-order traversals simultaneously uses two pointers with iterative in-order (smallest to largest) and reverse in-order (largest to smallest) traversals, allowing pair search in O(n) time and O(h) space. Other options use extra space O(n) or nested loops with O(n^2) time.

3. Final Answer:

   Use two pointers with iterative in-order and reverse in-order traversals simultaneously -> Option A

4. Quick Check:

   Two pointer BST traversal = O(n) time, O(h) space [OK]

Hint: Use two pointers with in-order and reverse in-order iterators [OK]

Common Mistakes:

• Using nested loops causing O(n^2) time
• Storing all nodes in list increasing space to O(n)
• Using BFS which uses more space than O(h)