Two Sum in BST in DSA Typescript - Execution Trace

Concept Flow - Two Sum in BST

Start at root node

↓

Initialize empty set for complements

↓

Inorder traversal: go left

↓

Visit node: check if complement exists in set

↓

Return true

↓

Traverse right

↓

Repeat until all nodes visited or pair found

↓

If no pair found, return false

Traverse BST inorder, check if complement of current node value exists in a set; if yes, return true, else add value and continue.

Execution Sample

DSA Typescript

function findTarget(root: TreeNode | null, k: number): boolean {
  const set = new Set<number>();
  function inorder(node: TreeNode | null): boolean {
    if (!node) return false;
    if (inorder(node.left)) return true;
    if (set.has(k - node.val)) return true;
    set.add(node.val);
    return inorder(node.right);
  }
  return inorder(root);
}

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

Execution Table

Step	Operation	Current Node Value	Set Contents	Action	Visual State
1	Start at root	5	{}	Traverse left subtree	5 / \ 3 6 / \ 2 4 7
2	Traverse left	3	{}	Traverse left subtree	5 / \ 3 6 / \ 2 4 7
3	Traverse left	2	{}	Traverse left subtree	5 / \ 3 6 / \ 2 4 7
4	Visit node	2	{}	Check complement 9 - 2 = 7 in set? No	5 / \ 3 6 / \ 2 4 7
5	Add to set	2	{2}	Add 2 to set	5 / \ 3 6 / \ 2 4 7
6	Traverse right	null	{2}	No right child, backtrack	5 / \ 3 6 / \ 2 4 7
7	Visit node	3	{2}	Check complement 9 - 3 = 6 in set? No	5 / \ 3 6 / \ 2 4 7
8	Add to set	3	{2,3}	Add 3 to set	5 / \ 3 6 / \ 2 4 7
9	Traverse right	4	{2,3}	Traverse right subtree	5 / \ 3 6 / \ 2 4 7
10	Visit node	4	{2,3}	Check complement 9 - 4 = 5 in set? No	5 / \ 3 6 / \ 2 4 7
11	Add to set	4	{2,3,4}	Add 4 to set	5 / \ 3 6 / \ 2 4 7
12	Traverse right	null	{2,3,4}	No right child, backtrack	5 / \ 3 6 / \ 2 4 7
13	Visit node	5	{2,3,4}	Check complement 9 - 5 = 4 in set? Yes	5 / \ 3 6 / \ 2 4 7
14	Return	5	{2,3,4}	Pair found (5 + 4 = 9), return true	5 / \ 3 6 / \ 2 4 7

💡 At step 13, complement 4 found in set, so pair summing to 9 exists, traversal stops.

Variable Tracker

Variable	Start	After Step 5	After Step 8	After Step 11	After Step 13	Final
set	{}	{2}	{2,3}	{2,3,4}	{2,3,4}	{2,3,4}
current node	5	2	3	4	5	5
found pair	false	false	false	false	true	true

Key Moments - 3 Insights

Why do we check if (k - node.val) is in the set before adding node.val?

Because we want to find if a previously visited node's value complements the current node to sum to k. Checking first (step 13) ensures we detect the pair immediately without missing it.

Why do we use inorder traversal instead of any other traversal?

Inorder traversal visits nodes in ascending order for BST, but here it's mainly to visit all nodes systematically. The set handles complement checks, so traversal order doesn't affect correctness.

What happens if the BST is empty?

The traversal immediately returns false at step 1 because the root is null, so no nodes to check, no pairs possible.

Visual Quiz - 3 Questions

Look at the execution table, what is the set contents after step 8?

A {2,3}

B {2}

C {2,3,4}

D {}

💡 Hint

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

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

A Step 11

B Step 13

C Step 5

D Step 9

💡 Hint

Look for the step where 'Check complement' finds a value in the set.

If the target sum k was 10 instead of 9, what would happen at step 13?

A Complement 5 would be found in set, return true

B Complement 6 would be found, return true

C Complement 5 would not be found, continue traversal

D Traversal would stop immediately

💡 Hint

At step 13, node value is 5; check if (k - 5) is in set. For k=10, complement is 5.

Concept Snapshot

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

Full Transcript

This visualization shows how to find two numbers in a binary search tree that add up to a target sum k. We do an inorder traversal of the BST, visiting nodes from smallest to largest. At each node, we check if the complement (k minus current node's 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's value to the set and continue. The execution table tracks each step, showing the current node, the set contents, and actions taken. The variable tracker shows how the set and current node change over time. Key moments clarify why we check complements before adding values and what happens if the tree is empty. The quiz tests understanding of set contents and when the pair is found. The snapshot summarizes the approach in simple steps.