Two Sum in BST in DSA Typescript - 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 sorted structures like BSTs. Without this concept, checking pairs would be slow and wasteful, especially in large data sets. It shows how tree properties can speed up common tasks like finding pairs that add up to a number.

Where it fits

Before this, you should know what a Binary Search Tree is and basic tree traversal methods. After this, you can learn about more complex tree algorithms, balanced trees, or two-pointer techniques in arrays.

Mental Model

Core Idea

Use the BST's sorted nature to quickly find two nodes whose values add up to the target by simulating a two-pointer search.

Think of it like...

Imagine a sorted list of numbers written on a long ribbon. You hold one end in each hand and move inward to find two numbers that add up to your target. The BST lets you do this without unrolling the whole ribbon.

BST structure and two-pointer idea:

       5
      / \
     3   7
    / \   \
   2   4   8

Two pointers:
Left pointer starts at smallest (2), right pointer at largest (8).
Move pointers inward based on sum compared to target.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Search Trees

Concept: Learn what a BST is and how its structure organizes data.

A BST is a tree where each node has up to two children. Left child nodes have smaller values than the parent, right child nodes have larger values. This property helps us search quickly by deciding to go left or right at each step.

Result

You can find any value in a BST faster than in an unsorted tree, usually in time proportional to the tree height.

Understanding BST structure is key because it allows efficient searching, which is the foundation for solving Two Sum in BST.

2

Foundation

Basic Tree Traversal Techniques

Concept: Learn how to visit all nodes in a BST using in-order traversal.

In-order traversal visits nodes in ascending order: left subtree, node, right subtree. This gives a sorted list of values from the BST.

Result

You get a sorted sequence of all node values, which can be used for searching pairs.

Knowing in-order traversal lets you convert the BST into a sorted list, bridging trees and arrays.

3

Intermediate

Two-Pointer Technique on Sorted Arrays

🤔Before reading on: do you think two pointers moving inward on a sorted array can find a pair summing to target faster than checking all pairs? Commit to yes or no.

Concept: Use two pointers at the start and end of a sorted array to find two numbers that sum to a target efficiently.

Start with one pointer at the smallest number and one at the largest. Calculate their sum. If sum is too small, move the left pointer right. If sum is too big, move the right pointer left. Repeat until pointers meet or pair found.

Result

You find the pair in linear time, much faster than checking all pairs.

This technique reduces complexity from quadratic to linear by leveraging sorted order.

4

Intermediate

Converting BST to Sorted Iterator

🤔Before reading on: do you think we need to store all BST values in an array to apply two-pointer technique? Commit to yes or no.

Concept: Create iterators that traverse the BST in ascending and descending order without storing all values.

Use two stacks to simulate in-order (left to right) and reverse in-order (right to left) traversals. Each iterator gives the next smallest or largest value on demand.

Result

You can get next smallest or largest BST value in O(h) time and O(h) space, where h is tree height.

This approach saves memory by not storing all values and allows two-pointer logic directly on the BST.

5

Intermediate

Applying Two-Pointer Logic on BST Iterators

🤔Before reading on: do you think the two iterators can be used together to find the target sum without converting BST to array? Commit to yes or no.

Concept: Use the two iterators to simulate two pointers moving inward on the BST values.

Initialize left iterator to smallest value and right iterator to largest. Compare their sum to target. If sum is less, advance left iterator. If sum is more, advance right iterator. Stop if pointers cross or pair found.

Result

You find if two nodes sum to target in O(n) time and O(h) space without extra array.

Combining BST iterators with two-pointer logic efficiently solves the problem using BST properties.

6

Advanced

TypeScript Implementation of Two Sum in BST

🤔Before reading on: do you think the code can run without storing all BST values explicitly? Commit to yes or no.

Concept: Implement the two iterator approach in TypeScript with clear code and comments.

class BSTIterator { private stack: TreeNode[] = []; private forward: boolean; constructor(root: TreeNode | null, forward: boolean) { this.forward = forward; this.pushAll(root); } next(): number | null { if (this.stack.length === 0) return null; const node = this.stack.pop()!; if (this.forward) this.pushAll(node.right); else this.pushAll(node.left); return node.val; } private pushAll(node: TreeNode | null) { while (node) { this.stack.push(node); node = this.forward ? node.left : node.right; } } } function findTarget(root: TreeNode | null, k: number): boolean { if (!root) return false; const leftIter = new BSTIterator(root, true); const rightIter = new BSTIterator(root, false); let left = leftIter.next(); let right = rightIter.next(); while (left !== null && right !== null && left < right) { const sum = left + right; if (sum === k) return true; else if (sum < k) left = leftIter.next(); else right = rightIter.next(); } return false; }

Result

The function returns true if two nodes sum to target, false otherwise.

Seeing the full code clarifies how iterators and two-pointer logic combine in practice.

7

Expert

Optimizing for Balanced and Unbalanced BSTs

🤔Before reading on: do you think this approach works equally well on very unbalanced BSTs? Commit to yes or no.

Concept: Understand how tree shape affects time and space complexity and how to optimize.

In balanced BSTs, height h is about log n, so space and time are efficient. In unbalanced BSTs (like linked lists), h can be n, making iterators costly. To optimize, consider balancing the tree first or using hash sets for lookup instead.

Result

You know when this method is efficient and when alternative methods are better.

Knowing tree shape impact helps choose the best algorithm for Two Sum in BST in real-world scenarios.

Under the Hood

The solution uses two controlled traversals of the BST: one in ascending order and one in descending order. Each traversal uses a stack to remember nodes to visit next, simulating pointers moving inward on a sorted list. By comparing values from both ends, it finds pairs summing to the target without storing all values.

Why designed this way?

Storing all BST values wastes memory and time. Using iterators leverages BST's sorted property and reduces space from O(n) to O(h). This design balances time and space efficiency, especially for large trees.

BST Iterators Flow:

  [BST Root]
     /    \
  LeftIter  RightIter
     |          |
  Stack L    Stack R
     |          |
  Next Small  Next Large
     \          /
      Compare Sum
         /     \
    Move Left  Move Right
    Iterator   Iterator

Myth Busters - 3 Common Misconceptions

Quick: Do you think storing all BST values in an array is always the best way to solve Two Sum? Commit yes or no.

Common Belief: It's easiest and best to convert the BST to a sorted array and then use two pointers.

Reality: Converting to an array uses extra memory and can be inefficient for large trees. Using BST iterators saves space and can be faster.

Why it matters: Relying on arrays can cause high memory use and slow performance in big data, making solutions impractical.

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

Common Belief: You can just pick any two nodes in the BST and check sums without traversal order.

Reality: BST nodes are not linked in sorted order, so you must traverse in order to simulate two pointers correctly.

Why it matters: Ignoring traversal order leads to incorrect or inefficient solutions.

Quick: Do you think this method works equally well on all BST shapes? Commit yes or no.

Common Belief: The two iterator method is always efficient regardless of tree shape.

Reality: In very unbalanced BSTs, iterator stacks can grow large, making the method less efficient.

Why it matters: Not considering tree shape can cause unexpected slowdowns in production.

Expert Zone

1

The iterator stacks only store nodes along the path to the next smallest or largest node, not the whole tree, optimizing memory.

2

Advancing one iterator depends on the sum comparison, so the algorithm dynamically balances traversal from both ends.

3

The method can be adapted to other ordered tree structures or even infinite streams with similar iterator logic.

When NOT to use

Avoid this approach if the BST is highly unbalanced or if you need to find all pairs, not just one. In such cases, using a hash set to store visited values or balancing the tree first is better.

Production Patterns

In real systems, this method is used in database indexing and search engines where data is stored in BST-like structures. It helps quickly find matching pairs without full scans or extra memory.

Connections

Two-Pointer Technique in Arrays

Builds-on

Understanding two pointers on arrays helps grasp how BST iterators simulate the same logic on tree data.

In-Order Tree Traversal

Builds-on

Knowing in-order traversal is essential because it produces the sorted sequence that the two-pointer logic relies on.

Database Indexing

Application

BSTs and their traversal methods underpin many database index structures, so this problem connects to efficient data retrieval in databases.

Common Pitfalls

#1 Storing all BST values in an array before searching pairs.

Wrong approach:

function findTarget(root, k) {
const values = [];
function inorder(node) {
if (!node) return;
inorder(node.left);
values.push(node.val);
inorder(node.right);
}
inorder(root);
let left = 0, right = values.length - 1;
while (left < right) {
const sum = values[left] + values[right];
if (sum === k) return true;
else if (sum < k) left++;
else right--;
}
return false;
}

Correct approach:

Use BST iterators to avoid storing all values:
class BSTIterator { ... } // as above
function findTarget(root, k) { ... } // as above

Root cause:

Assuming arrays are always simpler without considering memory and performance tradeoffs.

#2 Trying to move pointers without traversal order, picking random nodes.

Wrong approach:

function findTarget(root, k) {
// Randomly pick nodes and check sums without order
// No traversal logic
return false;
}

Correct approach:

Use controlled in-order and reverse in-order traversal to simulate pointers:
class BSTIterator { ... } // as above
function findTarget(root, k) { ... } // as above

Root cause:

Not understanding BST's sorted property and traversal necessity.

#3 Ignoring tree shape and expecting consistent performance.

Wrong approach:

Use the iterator method blindly on a skewed BST without balancing or alternative methods.

Correct approach:

Check tree balance first; if skewed, consider balancing or hash set approach:
function findTargetWithHash(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);
return dfs(node.left) || dfs(node.right);
}
return dfs(root);
}

Root cause:

Overlooking how tree structure affects algorithm efficiency.

Key Takeaways

Two Sum in BST uses the tree's sorted property to find pairs efficiently without extra memory for all values.

BST iterators simulate two pointers by traversing the tree in ascending and descending order using stacks.

This approach balances time and space complexity, especially in balanced trees, but may slow down in unbalanced trees.

Understanding traversal and two-pointer techniques together unlocks efficient solutions for many tree-based problems.

Choosing the right method depends on tree shape and problem constraints, highlighting the importance of algorithm adaptability.