Two Sum in BST in DSA Typescript - 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 whose values add up to a given target sum.

intermediate

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

Because BST nodes are ordered, we can efficiently search for complements using in-order traversal or two-pointer techniques.

beginner

What traversal method is commonly used to get sorted node values from a BST?

In-order traversal, which visits nodes in ascending order of their values.

intermediate

Explain the two-pointer technique in the context of Two Sum in BST.

After getting sorted values from BST, use two pointers at start and end to check sums. Move pointers inward based on sum comparison to target.

intermediate

What is the time complexity of the Two Sum in BST solution using in-order traversal and two pointers?

O(n), where n is the number of nodes, because we traverse all nodes once and then use two pointers on the sorted list.

Which traversal gives sorted node values in a BST?

A In-order traversal

B Pre-order traversal

C Post-order traversal

D Level-order traversal

In-order traversal visits BST nodes in ascending order.

What does the two-pointer technique do in Two Sum in BST?

A Checks pairs from start and end of sorted values to find target sum

B Searches each node's children recursively

C Builds a hash map of node values

D Deletes nodes that don't match the sum

Two pointers start at beginning and end of sorted list and move inward to find the sum.

What is the space complexity of storing BST values in a list for Two Sum?

A O(1)

B O(log n)

C O(n)

D O(n log n)

We store all node values in a list, so space is O(n).

If BST has 7 nodes, what is the maximum number of pairs checked by two-pointer method?

A 7

B Less than 7

C 3

D 6

Two pointers move inward, checking fewer than n pairs.

Which data structure can be used as an alternative to two-pointer for Two Sum in BST?

A Linked list

B Queue

C Stack

D Hash set

A hash set can store visited values to check complements in O(1).

Describe the step-by-step approach to solve Two Sum in BST using in-order traversal and two pointers.

Think about how sorted order helps find pairs efficiently.

Explain why the BST property helps reduce the search space in the Two Sum problem compared to an unsorted tree.

Focus on ordering and how it simplifies searching.