Two Sum in BST in DSA Go - Build from Scratch

Two Sum in BST

📖 Scenario: You are working with a phone book stored as a Binary Search Tree (BST). Each node contains a phone number. You want to find if there are two phone numbers in the BST that add up to a specific target sum.

🎯 Goal: Build a program that creates a BST with given phone numbers, sets a target sum, checks if any two numbers in the BST add up to the target, and prints the result.

📋 What You'll Learn

Create a BST with exact phone numbers: 10, 5, 15, 3, 7, 18

Create a variable called target with value 22

Write a function findTarget that returns true if two numbers in the BST add up to target

Print true or false depending on the result

💡 Why This Matters

🌍 Real World

Finding pairs of numbers that sum to a target is useful in financial applications, phone number analysis, and data validation.

💼 Career

This problem helps prepare for coding interviews and teaches tree traversal and hash map usage, common in software engineering roles.

1

Create the BST nodes

Create a struct type called TreeNode with fields Val int, Left *TreeNode, and Right *TreeNode. Then create the BST root node called root with value 10, and add nodes with values 5, 15, 3, 7, and 18 as shown in the example.

DSA Go

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

// Create the BST nodes below

Hint

Define the TreeNode struct first. Then create the root node and link child nodes to build the BST.

2

Set the target sum

Create an integer variable called target and set it to 22.

DSA Go

package main

import "fmt"

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

func main() {
    root := &TreeNode{Val: 10}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 15}
    root.Left.Left = &TreeNode{Val: 3}
    root.Left.Right = &TreeNode{Val: 7}
    root.Right.Right = &TreeNode{Val: 18}

    // Create the target variable below
    // Your code here
}

Hint

Just write target := 22 inside the main function.

3

Write the function to find two sum in BST

Write a function called findTarget that takes root *TreeNode and k int as parameters and returns bool. Use a map to store visited values and check if k - current node value exists. Traverse the BST recursively.

DSA Go

package main

import "fmt"

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

func main() {
    root := &TreeNode{Val: 10}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 15}
    root.Left.Left = &TreeNode{Val: 3}
    root.Left.Right = &TreeNode{Val: 7}
    root.Right.Right = &TreeNode{Val: 18}

    target := 22

    // Write the findTarget function call below
    // Your code here
}

// Write the findTarget function below

Hint

Use a helper function dfs inside findTarget to traverse the tree recursively. Use a map to check if the complement exists.

4

Print the result

Print the value of result using fmt.Println(result).

DSA Go

package main

import "fmt"

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

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

func main() {
    root := &TreeNode{Val: 10}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 15}
    root.Left.Left = &TreeNode{Val: 3}
    root.Left.Right = &TreeNode{Val: 7}
    root.Right.Right = &TreeNode{Val: 18}

    target := 22

    result := findTarget(root, target)

    // Print the result below
    // Your code here
}

Hint

Use fmt.Println(result) to print the boolean result.