Two Sum in BST in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Sum in BST with target 9

Given the BST below and target = 9, what is the output of the Two Sum function that returns true if two nodes sum to the target?

DSA Go

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

func findTarget(root *TreeNode, k int) bool {
    seen := make(map[int]bool)
    var dfs func(node *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)
}

// BST structure:
//       5
//      / \
//     3   6
//    / \   \
//   2   4   7

root := &TreeNode{5, &TreeNode{3, &TreeNode{2, nil, nil}, &TreeNode{4, nil, nil}}, &TreeNode{6, nil, &TreeNode{7, nil, nil}}}
result := findTarget(root, 9)
fmt.Println(result)

A true

B false

C runtime error

D compilation error

💡 Hint

Think about pairs of nodes that add up to 9 in the BST.

The function uses a map to track seen values. It finds 2 and 7 which sum to 9, so returns true.

🧠 Conceptual

intermediate

What data structure helps find two sum in BST efficiently?

Which data structure is most useful to check if the complement of a node's value exists while traversing a BST for two sum?

A Hash Map

B Queue

C Stack

D Linked List

💡 Hint

Think about fast lookup of complements.

A hash map allows O(1) average time lookup to check if complement exists.

🔧 Debug

advanced

Identify the error in Two Sum BST code snippet

What error does this Go code produce when run? func findTarget(root *TreeNode, k int) bool { seen := make(map[int]bool) var dfs func(node *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) }

A Runtime panic due to nil pointer

B Compilation error due to missing return

C Returns false even if pair exists

D Returns true always

💡 Hint

Check the boolean operator used in recursion return.

Using && requires both left and right to be true, so it misses pairs found in only one subtree.

🚀 Application

advanced

How many pairs sum to 10 in this BST?

Given the BST below, how many unique pairs of nodes sum to 10? // BST: // 8 // / \ // 3 10 // / \ \ // 1 6 14 // / \ / // 4 7 13

A 5

B 3

C 4

D 2

💡 Hint

Check pairs like (3,7), (6,4), (1,9) but 9 is not in tree.

Pairs summing to 10 are (3,7), (6,4), and (10,0) but 0 not in tree, so only 2 pairs. Actually (8,2) no 2 in tree. Also (14,-4) no negative. So only (3,7) and (6,4). Wait, 13+? No. So 2 pairs.

📝 Syntax

expert

Which option correctly implements Two Sum in BST using inorder traversal?

Select the correct Go code snippet that uses inorder traversal and two pointers to find if two nodes sum to target k in a BST.

A

func findTarget(root *TreeNode, k int) bool {
    vals := []int{}
    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Right)
        vals = append(vals, node.Val)
        inorder(node.Left)
    }
    inorder(root)
    left, right := 0, len(vals)-1
    for left < right {
        sum := vals[left] + vals[right]
        if sum == k {
            return true
        } else if sum < k {
            right--
        } else {
            left++
        }
    }
    return false
}

B

func findTarget(root *TreeNode, k int) bool {
    vals := []int{}
    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        vals = append(vals, node.Val)
        inorder(node.Right)
    }
    inorder(root)
    left, right := 0, len(vals)-1
    for left < right {
        sum := vals[left] + vals[right]
        if sum == k {
            return true
        } else if sum < k {
            left++
        } else {
            right--
        }
    }
    return false
}

C

}
eslaf nruter    
}    
}        
--thgir            
{ esle }        
++tfel            
{ k < mus fi esle }        
eurt nruter            
{ k == mus fi        
]thgir[slav + ]tfel[slav =: mus        
{ thgir < tfel rof    
1-)slav(nel ,0 =: thgir ,tfel    
)toor(redroni    
}    
)thgiR.edon(redroni        
)laV.edon ,slav(dneppa = slav        
)tfeL.edon(redroni        
}        
nruter            
{ lin == edon fi        
{ )edoNeerT* edon(cnuf = redroni    
)edoNeerT* edon(cnuf redroni rav    
}{tni][ =: slav    
{ loob )tni k ,edoNeerT* toor(tegraTdnif cnuf

D

func findTarget(root *TreeNode, k int) bool {
    vals := []int{}
    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        vals = append(vals, node.Val)
        inorder(node.Right)
    }
    inorder(root)
    left, right := 0, len(vals)-1
    for left < right {
        sum := vals[left] + vals[right]
        if sum == k {
            return true
        } else if sum > k {
            right--
        } else {
            left++
        }
    }
    return false
}

💡 Hint

Inorder traversal gives sorted array; use two pointers moving inward.

Option B correctly does inorder traversal (left-root-right) to get sorted values, then uses two pointers moving inward to find sum k.

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