Two Sum in BST in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Two Sum problem in a Binary Search Tree (BST)?

To find if there exist two nodes in the BST such that their values add up to a given target sum.

intermediate

Why is BST property useful in solving the Two Sum problem efficiently?

Because BST nodes are ordered, we can use two pointers (one from smallest, one from largest) to find the target sum without checking all pairs.

beginner

What data structure can be used to store visited node values to find the complement for Two Sum in BST?

A hash set can be used to store visited values and quickly check if the complement (target - current node value) exists.

advanced

Explain the two-pointer approach for Two Sum in BST.

Use an iterator to get the smallest value (inorder traversal) and another iterator for the largest value (reverse inorder traversal). Move pointers inward based on sum comparison with target.

intermediate

What is the time complexity of the Two Sum in BST using the two-pointer approach?

O(n), where n is the number of nodes, because each node is visited at most once by the two iterators.

What traversal is used to get nodes in ascending order in a BST?

A Level order traversal

B Preorder traversal

C Postorder traversal

D Inorder traversal

Inorder traversal visits nodes in ascending order for BST.

Which data structure helps check if a complement value exists quickly during Two Sum in BST?

A Queue

B Stack

C Hash set

D Linked list

Hash set allows O(1) average time lookup for complements.

In the two-pointer approach for Two Sum in BST, what does moving the left pointer forward mean?

A Checking larger values

B Checking random values

C Checking smaller values

D Stopping the search

Moving left pointer forward moves to larger values in ascending order.

What is the space complexity of using a hash set for Two Sum in BST?

A O(1)

B O(n)

C O(log n)

D O(n^2)

Hash set can store up to all node values, so O(n) space.

Which of these is NOT a valid approach to solve Two Sum in BST?

A Using binary search on unsorted array

B Using two pointers from smallest and largest nodes

C Brute force checking all pairs without BST property

D Using hash set to store visited values

Binary search requires sorted data; unsorted array is invalid here.

Describe how you would use two pointers to find two nodes in a BST that sum to a target.

Think about smallest and largest values in BST.

Explain how a hash set can help solve the Two Sum problem in a BST during a tree traversal.

Use extra memory to speed up complement lookup.