Two Sum in a BST Problem Statement

Given a Binary Search Tree (BST) and a target value, determine if there exists a pair of node values in the BST whose sum equals the target value.

Example:

Input:

4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1 9

Output:

True

Explanation:

Using the tree structure defined by the level order input, find two nodes such that their value sums up to the given target value, here 9.

Constraints:

1

Question

Given a Binary Search Tree (BST) and a target value, determine if there exists a pair of node values in the BST whose sum equals the target value.

4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1
9

True

Using the tree structure defined by the level order input, find two nodes such that their value sums up to the given target value, here 9.

You are expected to implement the function only. The input/output operations are handled for you.

Accepted Answer

Given a BST and a target value, find if there exists a pair of node values in the BST whose sum equals the target value.

Traverse the BST in-order and store the node values in a set while checking for the target value difference.
Use two pointers approach to find the pair of values that sum up to the target value.
Consider edge cases like negative values and handling duplicates in the BST.

Morgan Stanley Software Developer interview questions & answers