Two Sum in BST in DSA Go

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

Output

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.

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

3. Final Answer:

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

4. Quick Check:

   Two Sum in BST = Find pair with target sum [OK]

Hint: Look for two values that add up to target in BST [OK]

Common Mistakes:

• Confusing with finding max or min value
• Trying to count nodes instead of finding pairs
• Checking BST balance instead of sum pairs

2. Which of the following Go function signatures is correct for a function that checks if two sum exists in a BST?

easy

A. func findTarget(root *TreeNode, k int) bool

B. func findTarget(root TreeNode, k string) int

C. func findTarget(root *TreeNode, k float64) string

D. func findTarget(root TreeNode, k bool) *TreeNode

Solution

1. Step 1: Understand function parameters and return type

   The function should take a pointer to the root node of BST and an integer target sum, returning a boolean indicating if pair exists.

2. Step 2: Match correct signature

   func findTarget(root *TreeNode, k int) bool matches: pointer to TreeNode, integer target, returns bool.

3. Final Answer:

   func findTarget(root *TreeNode, k int) bool -> Option A

4. Quick Check:

   Correct function signature = func findTarget(root *TreeNode, k int) bool [OK]

Hint: Function takes *TreeNode and int, returns bool [OK]

Common Mistakes:

• Using wrong parameter types like string or bool
• Passing TreeNode by value instead of pointer
• Returning wrong type like int or string

3. What will be the output of the following Go code snippet for Two Sum in BST?

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}

func findTarget(root *TreeNode, k int) bool {
    seen := make(map[int]bool)
    var dfs func(*TreeNode) bool
    dfs = func(node *TreeNode) bool {
        if node == nil {
            return false
        }
        if seen[k - node.Val] {
            return true
        }
        seen[node.Val] = true
        return dfs(node.Left) || dfs(node.Right)
    }
    return dfs(root)
}

root := &TreeNode{Val:5, Left:&TreeNode{Val:3}, Right:&TreeNode{Val:6}}
result := findTarget(root, 9)
fmt.Println(result)

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Trace the DFS traversal and map usage

   The function uses DFS to traverse nodes. It checks if (target - current node value) is in the map. For root 5, seen is empty, adds 5. Goes left to 3, checks if 9-3=6 in seen (no), adds 3. Goes right to 6, checks if 9-6=3 in seen (yes), returns true.

2. Step 2: Confirm output

   Since pair (3,6) sums to 9, function returns true and prints true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Pair found (3+6=9) = true [OK]

Hint: Check if complement exists in map during DFS [OK]

Common Mistakes:

• Not checking complement before adding current value
• Returning false too early
• Ignoring nil node checks causing panic

4. Identify the bug in this Go code for Two Sum in BST and choose the fix:

func findTarget(root *TreeNode, k int) bool {
    seen := make(map[int]bool)
    var dfs func(*TreeNode) bool
    dfs = func(node *TreeNode) bool {
        if node == nil {
            return false
        }
        seen[node.Val] = true
        if seen[k - node.Val] {
            return true
        }
        return dfs(node.Left) || dfs(node.Right)
    }
    return dfs(root)
}

medium

A. Add a nil check after adding to map.

B. Remove the map and use a slice instead.

C. Change return type to int instead of bool.

D. Check complement before adding current node value to map.

Solution

1. Step 1: Analyze the order of operations in DFS

   The code adds current node value to map before checking if complement exists. This causes the complement check to always find current value, leading to false positives.

2. Step 2: Correct the order

   Check if complement exists in map before adding current node value to avoid matching the same node twice.

3. Final Answer:

   Check complement before adding current node value to map. -> Option D

4. Quick Check:

   Complement check before map insert fixes bug [OK]

Hint: Check complement before adding current value [OK]

Common Mistakes:

• Adding current value before checking complement
• Using wrong data structure for lookup
• Ignoring nil node checks

5. Given a BST with nodes [4, 2, 6, 1, 3, 5, 7], which pairs sum to 9? Select the correct output of a Two Sum in BST function that returns all pairs.

func findAllPairs(root *TreeNode, k int) [][2]int {
    seen := make(map[int]bool)
    pairs := [][2]int{}
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        complement := k - node.Val
        if seen[complement] {
            pairs = append(pairs, [2]int{complement, node.Val})
        }
        seen[node.Val] = true
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return pairs
}

hard

A. [[5,4],[6,3],[7,2]]

B. [[1,8],[2,7],[3,6]]

C. [[3,6],[4,5],[2,7]]

D. [[1,7],[2,6],[3,5]]

Solution

1. Step 1: Identify all pairs in BST that sum to 9

   Nodes are 1,2,3,4,5,6,7. Pairs summing to 9 are (2,7), (3,6), (4,5).

2. Step 2: Match pairs with function output format

   The function appends pairs as [complement, node.Val] during preorder traversal: at 6 finds 3 in seen, appends [3,6]; at 5 finds 4, [4,5]; at 7 finds 2, [2,7].

3. Final Answer:

   [[3,6],[4,5],[2,7]] -> Option C

4. Quick Check:

   Pairs summing to 9 in traversal order = [[3,6],[4,5],[2,7]] [OK]

Hint: List pairs where values sum to target k [OK]

Common Mistakes:

• Including pairs with values not in BST
• Reversing pair order incorrectly
• Missing valid pairs