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.

Practice

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

easy

A. Find the maximum value in the BST.

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

C. Count the total number of nodes in the BST.

D. Check if the BST is balanced.

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 max value, count nodes, or check balance.

3. Final Answer:

   Find two nodes in the 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 pairs adding to target in BST nodes [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare a BST node in JavaScript for the Two Sum problem?

easy

A. function Node(val) { this.val = val; this.left = null; this.right = null; }

B. let Node = (val) => { val = val; left = null; right = null; }

C. class Node { constructor(val) { val = val; left = null; right = null; } }

D. var Node = function(val) { this.value = val; this.left = this.right = undefined; }

Solution

1. Step 1: Check correct property assignments

   function Node(val) { this.val = val; this.left = null; this.right = null; } correctly assigns this.val, this.left, and this.right to initialize a BST node.

2. Step 2: Identify syntax and property errors in other options

   let Node = (val) => { val = val; left = null; right = null; } misses this keyword and uses arrow function incorrectly. class Node { constructor(val) { val = val; left = null; right = null; } } assigns to local variables, not this. var Node = function(val) { this.value = val; this.left = this.right = undefined; } uses this.value instead of this.val and sets children to undefined instead of null.

3. Final Answer:

   function Node(val) { this.val = val; this.left = null; this.right = null; } -> Option A

4. Quick Check:

   Correct node declaration uses this.val and null children [OK]

Hint: Use function with this.val, this.left, this.right = null [OK]

Common Mistakes:

• Forgetting 'this' keyword for properties
• Using arrow functions for constructor
• Assigning children to undefined instead of null

3. Given the BST below and target = 9, what will the function findTarget(root, 9) return?

    5
   / \
  3   6
 / \   \
2   4   7

Assuming findTarget returns true if two nodes sum to target, else false.

medium

A. true

B. false

C. null

D. undefined

Solution

1. Step 1: Identify pairs that sum to 9

   Check pairs: 2+7=9, 3+6=9, 4+5=9. All these pairs exist in the BST.

2. Step 2: Confirm function returns true if any pair matches

   Since pairs exist, findTarget returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Pairs sum to 9 = true [OK]

Hint: Check pairs adding to target in BST nodes [OK]

Common Mistakes:

• Ignoring valid pairs in BST
• Assuming function returns node instead of boolean
• Confusing null or undefined as return

4. Consider this buggy code snippet for Two Sum in BST:

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

What is the main bug causing incorrect results?

medium

A. Using Set instead of Array for storage

B. Checking for k - node.val before adding node.val

C. Missing return statements in recursive calls inside dfs

D. Not handling empty tree case

Solution

1. Step 1: Analyze recursive calls in dfs

   The recursive calls to dfs(node.left) and dfs(node.right) do not return their results, so true found deeper is ignored.

2. Step 2: Fix by returning recursive calls

   Adding return before recursive calls ensures if true is found, it propagates up and final result is correct.

3. Final Answer:

   Missing return statements in recursive calls inside dfs -> Option C

4. Quick Check:

   Return recursive calls to propagate true [OK]

Hint: Always return recursive calls to propagate results [OK]

Common Mistakes:

• Not returning recursive call results
• Confusing Set usage as bug
• Ignoring base case handling

5. You want to optimize the Two Sum in BST problem to use O(h) space, where h is tree height. Which approach is best?

hard

A. Convert BST to a linked list and then find pairs.

B. Store all node values in an array and use a hash set to find pairs.

C. Perform a breadth-first search and check pairs at each level.

D. Use two iterators: one in-order and one reverse in-order traversal simultaneously.

Solution

1. Step 1: Understand space complexity of approaches

   Storing all nodes uses O(n) space. BFS also uses O(n) space. Converting to linked list uses O(n).

2. Step 2: Use two iterators approach

   Using two iterators (one in-order for smallest, one reverse in-order for largest) uses O(h) space, where h is tree height, optimizing space.

3. Final Answer:

   Use two iterators: one in-order and one reverse in-order traversal simultaneously. -> Option D

4. Quick Check:

   Two iterators = O(h) space optimization [OK]

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

Common Mistakes:

• Using full array storage increasing space to O(n)
• Trying BFS which uses more space
• Converting BST to linked list wastes space