Two Sum in BST in DSA Javascript - Deep Dive

Overview - Two Sum in BST

What is it?

Two Sum in BST is a problem where you find if there are two numbers in a Binary Search Tree (BST) that add up to a given target number. A BST is a special tree where left children are smaller and right children are bigger than their parent. The goal is to check if any two nodes in this tree sum to the target.

Why it matters

This problem helps us understand how to efficiently search and combine data in a sorted structure like a BST. Without this concept, checking pairs would be slow and wasteful, especially for large trees. It shows how to use the BST's order to find answers faster, which is important in many real-world tasks like searching databases or solving puzzles.

Where it fits

Before this, you should know what a Binary Search Tree is and how to traverse it. After this, you can learn about more complex tree problems, like balancing trees or finding paths with certain sums.

Mental Model

Core Idea

Use the BST's sorted order to quickly find two nodes whose values add up to the target without checking every pair.

Think of it like...

Imagine you have a sorted list of prices in a store and want to find two items that together cost exactly your budget. Instead of trying every pair, you start with the cheapest and the most expensive and move inward until you find the right pair.

BST Inorder Traversal (sorted):

  [ 2, 3, 5, 7, 9, 12, 15 ]

Two pointers approach:

  left -> 2
  right -> 15

Sum = 17
If sum > target, move right pointer left
If sum < target, move left pointer right
Repeat until pointers meet or sum found

Build-Up - 6 Steps

1

Foundation

Understanding Binary Search Tree Basics

Concept: Learn what a BST is and how its structure keeps values sorted.

A Binary Search Tree is a tree where each node has up to two children. The left child has a smaller value, and the right child has a larger value than the node. This property makes it easy to find values quickly by comparing and moving left or right.

Result

You can find any value in a BST faster than in an unsorted tree by following left or right paths.

Understanding the BST property is key because it allows us to use sorted order to solve problems efficiently.

2

Foundation

Inorder Traversal Produces Sorted Values

Concept: Learn how to get all BST values in sorted order using inorder traversal.

Inorder traversal visits nodes in this order: left child, current node, right child. For a BST, this means visiting nodes from smallest to largest value. For example, a BST with nodes 5, 3, 7 will be visited as 3, 5, 7.

Result

You get a sorted list of all values in the BST.

Getting sorted values from the BST lets us use two-pointer techniques that work on sorted arrays.

3

Intermediate

Two Sum Problem in Sorted Array

🤔Before reading on: do you think checking all pairs or using two pointers is faster for finding two numbers that sum to target in a sorted list? Commit to your answer.

Concept: Learn the two-pointer technique to find two numbers that add up to a target in a sorted list.

Start with two pointers: one at the start (smallest) and one at the end (largest). Calculate their sum. If sum equals target, done. If sum is less, move left pointer right to increase sum. If sum is more, move right pointer left to decrease sum. Repeat until pointers meet.

Result

You find the pair in O(n) time instead of O(n²) by checking all pairs.

Knowing this technique is crucial because it reduces time complexity drastically and is the core of solving Two Sum in BST efficiently.

4

Intermediate

Applying Two Pointers to BST Using Iterators

🤔Before reading on: do you think we can apply two-pointer technique directly on BST nodes without converting to array? Commit to yes or no.

Concept: Use two iterators to simulate two pointers on BST without extra space for array.

Create two iterators: one that does inorder traversal (smallest to largest) and one that does reverse inorder traversal (largest to smallest). Each iterator gives the next smallest or largest value on demand. Move iterators inward like two pointers until sum matches target or they cross.

Result

You can find two sum in BST in O(n) time and O(h) space, where h is tree height, without building a full array.

This approach saves memory and uses BST structure directly, showing how to adapt array techniques to trees.

5

Advanced

Implementing BST Iterators in JavaScript

🤔Before reading on: do you think stack is needed to implement BST iterators for inorder and reverse inorder? Commit to yes or no.

Concept: Use a stack to implement controlled traversal of BST for next smallest or largest value.

For inorder iterator, push left children until none left, then pop and move to right child. For reverse inorder, push right children until none left, then pop and move to left child. Each next() call returns current node value and prepares next node.

Result

You get a reusable iterator that returns next smallest or largest BST value on demand.

Understanding stack-based traversal is key to efficient BST iteration without recursion or full traversal.

6

Expert

Optimizing Two Sum in BST for Large Trees

🤔Before reading on: do you think building a full sorted array is better than using iterators for very large BSTs? Commit to your answer.

Concept: Trade-offs between memory and speed when choosing between full array conversion and iterator approach.

Building a full sorted array uses O(n) memory but allows simple two-pointer search. Iterator approach uses O(h) memory but may be slower due to repeated stack operations. For very large trees, iterator approach is memory efficient but may have overhead. Choose based on constraints.

Result

You understand when to use each method depending on tree size and memory limits.

Knowing these trade-offs helps write scalable code and avoid memory issues in production.

Under the Hood

The BST property ensures inorder traversal visits nodes in ascending order. Two iterators use stacks to simulate controlled traversal: one from smallest to largest, the other from largest to smallest. Each iterator maintains its own stack of nodes to visit next. By comparing current values from both iterators, we decide which iterator to advance, effectively simulating two pointers on a sorted array without extra memory for the array.

Why designed this way?

This design leverages BST's sorted nature to avoid checking all pairs, which would be O(n²). Using iterators with stacks allows lazy traversal, saving memory compared to building a full sorted list. Historically, this approach balances time and space efficiency, especially important for large trees where memory is limited.

BST Two Sum Iterators:

  [BST Root]
     /    \
  ...      ...

Inorder Iterator Stack: [nodes to visit next smallest]
Reverse Inorder Iterator Stack: [nodes to visit next largest]

Compare values from both iterators:
  If sum == target -> found
  If sum < target -> advance inorder iterator
  If sum > target -> advance reverse inorder iterator

Repeat until iterators meet or pair found.

Myth Busters - 3 Common Misconceptions

Quick: Do you think converting BST to array is always the best way to solve Two Sum? Commit yes or no.

Common Belief: Converting the BST to an array first is always the simplest and best solution.

Reality: While converting to an array is simple, it uses O(n) extra space. Using two BST iterators can solve the problem with O(h) space, where h is tree height, which is more memory efficient.

Why it matters: Using too much memory can cause problems in large systems or with big trees, leading to crashes or slowdowns.

Quick: Do you think the two-pointer technique works directly on BST nodes without traversal? Commit yes or no.

Common Belief: You can apply two-pointer technique directly on BST nodes without any traversal or extra data structures.

Reality: BST nodes are not linked like an array, so you cannot move pointers left or right directly. You must traverse the tree in order or reverse order using stacks or recursion to simulate pointers.

Why it matters: Trying to move pointers directly on BST nodes leads to incorrect or inefficient code.

Quick: Do you think the two iterators can cross each other and still find a valid pair? Commit yes or no.

Common Belief: The two iterators can cross and still find a valid pair that sums to the target.

Reality: Once the two iterators cross, it means all pairs have been checked. No valid pair exists beyond this point.

Why it matters: Not stopping when iterators cross causes infinite loops or wrong answers.

Expert Zone

1

BST iterator stacks only store nodes along the current path, not the entire tree, making space usage proportional to tree height, not size.

2

Reverse inorder traversal is less intuitive but essential for the two-pointer approach on BST, as it simulates moving from the largest value downward.

3

When the BST is unbalanced, the height can approach n, making iterator space O(n), so balancing the tree improves performance.

When NOT to use

Avoid this approach if the BST is extremely unbalanced or if you need to find multiple pairs quickly. In such cases, converting to a balanced structure or using hashing might be better alternatives.

Production Patterns

In real systems, this pattern is used in database indexing where range queries and sum checks are common. Also used in coding interviews to test understanding of BST traversal and two-pointer techniques combined.

Connections

Two Sum in Sorted Array

Two Sum in BST builds on the two-pointer technique used in sorted arrays.

Understanding two-pointer in arrays helps grasp how BST iterators simulate pointers on a sorted structure.

Inorder and Reverse Inorder Traversal

Two Sum in BST uses these traversals as building blocks for iterators.

Mastering these traversals is essential to implement efficient BST iterators.

Database Indexing

BSTs and their traversal methods relate to how databases index and search data efficiently.

Knowing BST two sum techniques helps understand how databases optimize range and sum queries.

Common Pitfalls

#1 Trying to move pointers directly on BST nodes without traversal.

Wrong approach:

let left = root.left; let right = root.right; while(left !== right) { if(left.val + right.val === target) return true; left = left.right; right = right.left; }

Correct approach:

Use two iterators with stacks to traverse inorder and reverse inorder, advancing them based on sum comparison.

Root cause:

Misunderstanding that BST nodes are not linked like array elements and cannot be moved left or right directly.

#2 Converting BST to array but forgetting to check for duplicates or stopping conditions.

Wrong approach:

const arr = []; function inorder(node) { if(!node) return; inorder(node.left); arr.push(node.val); inorder(node.right); } inorder(root); for(let i=0; i

Correct approach:

Use two-pointer technique on the sorted array to find the pair in O(n) time.

Root cause:

Not using the efficient two-pointer method leads to O(n²) time complexity.

#3 Not stopping iteration when iterators cross, causing infinite loop.

Wrong approach:

while(true) { let sum = leftIterator.val + rightIterator.val; if(sum === target) return true; else if(sum < target) leftIterator.next(); else rightIterator.next(); }

Correct approach:

Stop when leftIterator and rightIterator point to the same node or cross each other.

Root cause:

Ignoring the termination condition of the two-pointer approach on BST iterators.

Key Takeaways

Two Sum in BST uses the tree's sorted order property to find pairs efficiently.

Inorder and reverse inorder traversals simulate two pointers moving inward from smallest and largest values.

Using iterators with stacks avoids extra memory usage compared to converting the BST to an array.

Stopping conditions are critical to avoid infinite loops when iterators cross.

Choosing between array conversion and iterator approach depends on memory and performance needs.

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