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.