Two Sum in BST in DSA Javascript - Execution Trace

Concept Flow - Two Sum in BST

Start at root

↓

Initialize two pointers

↓

Left pointer = smallest node

↓

Right pointer = largest node

↓

Check sum = left.val + right.val

↓

Return true

↓

Move left pointer to next larger node

↓

Move right pointer to next smaller node

↓

Repeat until pointers meet

↓

Return false if no pair found

We use two pointers starting at smallest and largest nodes in the BST, moving inward to find two nodes summing to target.

Execution Sample

DSA Javascript

function findTarget(root, k) {
  let left = getMinNode(root);
  let right = getMaxNode(root);
  while (left !== right) {
    let sum = left.val + right.val;
    if (sum === k) return true;
    else if (sum < k) left = getNextLargerNode(left);
    else right = getNextSmallerNode(right);
  }
  return false;
}

This code tries to find two nodes in a BST whose values add up to k using two pointers moving inward.

Execution Table

Step	Operation	Left Pointer Node	Right Pointer Node	Sum	Action	Visual State
1	Initialize pointers	Node(2)	Node(9)	2 + 9 = 11	11 > 7, move right pointer left	2 -> 3 -> 5 -> 7 -> 9
2	Move right pointer	Node(2)	Node(7)	2 + 7 = 9	9 > 7, move right pointer left	2 -> 3 -> 5 -> 7 -> 9
3	Move right pointer	Node(2)	Node(5)	2 + 5 = 7	7 == 7, return true	2 -> 3 -> 5 -> 7 -> 9
4	Return	-	-	-	Found pair (2,5) equals target 7	2 -> 3 -> 5 -> 7 -> 9

💡 Pointers met or found pair summing to target; here pair (2,5) sums to 7, so return true.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
left	Node(2)	Node(2)	Node(2)	Node(2)	Node(2)
right	Node(9)	Node(9)	Node(7)	Node(5)	Node(5)
sum	-	11	9	7	7

Key Moments - 3 Insights

Why do we move the right pointer left when sum is greater than target?

Because the BST is sorted, moving the right pointer to the next smaller node decreases the sum, as shown in steps 1 and 2 in the execution_table.

Why do we stop when left and right pointers meet?

When both pointers meet, it means all pairs have been checked without finding the target sum, so we stop. In this example, we found the pair before they met (step 3).

How do we find the next larger or smaller node in BST?

We use in-order traversal logic: next larger node is the in-order successor, next smaller node is the in-order predecessor. This is implied in pointer moves in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the value of the right pointer node?

A Node(7)

B Node(5)

C Node(9)

D Node(2)

💡 Hint

Check the 'Right Pointer Node' column at step 2 in the execution_table.

At which step does the sum equal the target value 7?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Sum' and 'Action' columns in the execution_table to find when sum == target.

If the target was 10 instead of 7, what would happen at step 3?

A Move right pointer to next smaller node

B Return true because sum equals target

C Move left pointer to next larger node

D Stop immediately

💡 Hint

Refer to the 'Action' column logic in the execution_table for sum < target cases.

Concept Snapshot

Two Sum in BST:
- Use two pointers: left at smallest node, right at largest node
- Calculate sum = left.val + right.val
- If sum == target, return true
- If sum < target, move left pointer to next larger node
- If sum > target, move right pointer to next smaller node
- Stop when pointers meet or pair found

Full Transcript

The Two Sum in BST problem uses two pointers starting at the smallest and largest nodes of the BST. We calculate the sum of their values. If the sum equals the target, we return true. If the sum is less than the target, we move the left pointer to the next larger node to increase the sum. If the sum is greater than the target, we move the right pointer to the next smaller node to decrease the sum. We repeat this until the pointers meet or we find a pair that sums to the target. This approach leverages the BST's sorted property to efficiently find the pair without checking all nodes.

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