Two Sum in BST in DSA Go - Execution Trace

Concept Flow - Two Sum in BST

Start at root

↓

Initialize empty set

↓

Inorder traversal node

↓

Check if complement exists in set

↓

Return true

↓

Move to next node

↓

Repeat until all nodes visited or found

↓

Return false if no pair found

Traverse the BST in order, check if complement of current node value exists in a set, return true if found, else add value and continue.

Execution Sample

DSA Go

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

This code checks if there exist two nodes in BST whose values sum to k using inorder traversal and a set.

Execution Table

Step	Operation	Current Node Value	Set Contents	Check Complement	Action	Visual State
1	Start at root	5	{}	Check if 9 - 5 = 4 in set	4 not in set, add 5	5
2	Go left	3	{5}	Check if 9 - 3 = 6 in set	6 not in set, add 3	3 -> 5
3	Go left	2	{3,5}	Check if 9 - 2 = 7 in set	7 not in set, add 2	2 -> 3 -> 5
4	Left nil	nil	{2,3,5}	N/A	Return false	2 -> 3 -> 5
5	Back to 2	2	{2,3,5}	Already processed	Go right	2 -> 3 -> 5
6	Right nil	nil	{2,3,5}	N/A	Return false	2 -> 3 -> 5
7	Back to 3	3	{2,3,5}	Already processed	Go right	2 -> 3 -> 5
8	Go right	4	{2,3,5}	Check if 9 - 4 = 5 in set	5 found! Return true	4 -> 3 -> 5
9	Found pair (4,5)	N/A	{2,3,5}	N/A	Stop traversal	4 -> 3 -> 5

💡 Found complement 5 for node 4, sum 9 achieved, traversal stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 8	Final
Current Node	root (5)	3	2	4	4	N/A
Set Contents	{}	{5}	{3,5}	{2,3,5}	{2,3,5}	{2,3,5}
Return Value	false	false	false	false	true	true

Key Moments - 3 Insights

Why do we check if complement exists before adding current node value to the set?

Because checking complement first avoids pairing a node with itself. See step 8 in execution_table where complement 5 is found before adding 4.

Why do we use inorder traversal for this problem?

Inorder traversal visits nodes in ascending order, but here it mainly ensures all nodes are visited systematically. The set handles complement checks. See steps 1-9 for traversal order.

What happens if the BST is empty?

The traversal immediately returns false since root is nil, no nodes to check. This is implied at step 4 when node is nil and returns false.

Visual Quiz - 3 Questions

Look at the execution_table, what is the set contents after step 3?

A {}

B {5}

C {3,5}

D {2,3,5}

💡 Hint

Check the 'Set Contents' column at step 3 in execution_table.

At which step does the traversal find the pair that sums to 9?

A Step 4

B Step 6

C Step 8

D Step 9

💡 Hint

Look for the step where 'Check if 9 - 4 = 5 in set' is true in execution_table.

If the target sum was 7 instead of 9, what would happen to the execution?

A Pair found earlier than step 8

B No pair found, traversal completes all nodes

C Traversal stops at step 3

D Set remains empty

💡 Hint

Consider how complement checks depend on target k and see variable_tracker for set contents.

Concept Snapshot

Two Sum in BST:
- Traverse BST inorder
- Use a set to store visited values
- For each node, check if (target - node.Val) in set
- If yes, return true
- Else add node.Val to set
- Return false if no pair found

Full Transcript

This visualization shows how to find two numbers in a BST that add up to a target sum. We start at the root and traverse the tree in order. At each node, we check if the complement (target minus current node value) is already in a set of visited values. If it is, we found a pair and return true. If not, we add the current node value to the set and continue. The traversal stops early if a pair is found. The execution table tracks each step, the current node, the set contents, and actions taken. Variable tracker shows how the current node and set change over time. Key moments clarify why we check complement before adding the node value and why inorder traversal is used. The quiz tests understanding of set contents and when the pair is found.