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. You look from the cheapest and the most expensive items moving inward to find the pair.

    5
   / \
  3   7
 / \   \
2   4   8

We want to find two nodes whose values add up to a 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: 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 cover the range

Step 2: Sum left + right = 2 + 8 = 10, which is greater than 9, move right pointer to next smaller (7)

Left = 2, Right = 7

Why: Sum too big, decrease right to get smaller sum

Step 3: Sum left + right = 2 + 7 = 9, equals target, found pair

Left = 2, Right = 7

Why: Sum matches target, so pair found

Result:

2 -> ... -> 7
Pair found: 2 + 7 = 9

Annotated Code

DSA Go

package main

import "fmt"

// TreeNode defines a node in BST
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// BSTIterator iterates over BST in ascending or descending order
type BSTIterator struct {
    stack    []*TreeNode
    forward  bool // true for ascending, false for descending
}

// NewBSTIterator creates iterator
func NewBSTIterator(root *TreeNode, forward bool) *BSTIterator {
    it := &BSTIterator{forward: forward}
    it.pushAll(root)
    return it
}

// pushAll pushes nodes to stack depending on direction
func (it *BSTIterator) pushAll(node *TreeNode) {
    for node != nil {
        it.stack = append(it.stack, node)
        if it.forward {
            node = node.Left
        } else {
            node = node.Right
        }
    }
}

// HasNext checks if iterator has next element
func (it *BSTIterator) HasNext() bool {
    return len(it.stack) > 0
}

// Next returns next element and advances iterator
func (it *BSTIterator) Next() int {
    n := len(it.stack) - 1
    node := it.stack[n]
    it.stack = it.stack[:n]
    if it.forward {
        it.pushAll(node.Right)
    } else {
        it.pushAll(node.Left)
    }
    return node.Val
}

// findTarget checks if two sum exists in BST
func findTarget(root *TreeNode, k int) bool {
    if root == nil {
        return false
    }
    leftIt := NewBSTIterator(root, true)  // ascending
    rightIt := NewBSTIterator(root, false) // descending

    leftVal := 0
    rightVal := 0

    if leftIt.HasNext() {
        leftVal = leftIt.Next() // smallest
    }
    if rightIt.HasNext() {
        rightVal = rightIt.Next() // largest
    }

    for leftVal < rightVal {
        sum := leftVal + rightVal
        if sum == k {
            return true
        } else if sum < k {
            if leftIt.HasNext() {
                leftVal = leftIt.Next() // move left forward
            } else {
                break
            }
        } else {
            if rightIt.HasNext() {
                rightVal = rightIt.Next() // move right backward
            } else {
                break
            }
        }
    }
    return false
}

func main() {
    // Construct BST
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 3}
    root.Right = &TreeNode{Val: 7}
    root.Left.Left = &TreeNode{Val: 2}
    root.Left.Right = &TreeNode{Val: 4}
    root.Right.Right = &TreeNode{Val: 8}

    target := 9
    found := findTarget(root, target)
    fmt.Printf("Two sum %d in BST? %v\n", target, found)
}

leftIt := NewBSTIterator(root, true)  // ascending
rightIt := NewBSTIterator(root, false) // descending

Initialize two iterators: one from smallest, one from largest

leftVal = leftIt.Next() // smallest
rightVal = rightIt.Next() // largest

Get initial values from both ends

for leftVal < rightVal {

Loop while pointers do not cross

sum := leftVal + rightVal

Calculate sum of current pair

if sum == k { return true }

If sum matches target, return true

else if sum < k { leftVal = leftIt.Next() }

If sum too small, move left pointer forward to increase sum

else { rightVal = rightIt.Next() }

If sum too big, move right pointer backward to decrease sum

OutputSuccess

Two sum 9 in BST? true

Complexity Analysis

Time: O(n) because in worst case we may visit all nodes once with two iterators

Space: O(h) where h is tree height due to stack space in iterators

vs Alternative: Naive approach checks all pairs O(n^2), this uses BST order to reduce to O(n)

Edge Cases

Empty tree

Returns false immediately, no pairs

DSA Go

if root == nil { return false }

Single node tree

No pair possible, returns false

DSA Go

for leftVal < rightVal { ... } ensures no false positives

No two nodes sum to target

Returns false after exhausting pairs

DSA Go

break conditions when iterators exhausted

When to Use This Pattern

When asked to find two numbers summing to target in a BST, use two-pointer iteration with BST iterators to leverage sorted order efficiently.

Common Mistakes

Mistake: Trying to convert BST to array first, wasting space and time
Fix: Use BST iterators to traverse without full conversion

Mistake: Not handling case when left and right pointers cross
Fix: Stop loop when leftVal >= rightVal to avoid invalid pairs

Summary

Finds if two nodes in BST sum to a target using two-pointer technique with BST iterators.

Use when you need to find pairs summing to a value efficiently in a BST.

The key insight is to traverse BST from smallest and largest simultaneously to check sums without extra space.