DSA interview question

Two Sum in a BST

Hard · Algorithms · Topics: bst, two pointer, hash set

The problem

A gift-card app stores item prices in a BST and must answer: do two different items cost exactly k in total? On a sorted array, the classic two-pointer technique solves this in O(n). A BST is a sorted array in disguise. Run a forward inorder iterator (smallest first) and a backward iterator (largest first) using two stacks, and move them toward each other just like two pointers. That uses O(h) memory instead of copying all n values.

Example: BST [5, 3, 6, 2, 4, null, 7], k = 9 → true (2 + 7, or 3 + 6, or 4 + 5).

Function signature

bool findTarget(TreeNode* root, int k);

Test cases

Input `(tree, k)`	Output	Explanation
`([5, 3, 6, 2, 4, null, 7], 9)`	`true`	2 + 7
`([5, 3, 6, 2, 4, null, 7], 28)`	`false`
`([2, 1, 3], 4)`	`true`	1 + 3
`([2, 1, 3], 1)`	`false`
`([1], 2)`	`false`	A node can't pair with itself

(Confirm: the two values must come from different nodes; keys are distinct.)

How interviewers phrase it

"Given the root of a BST and an integer k, return true if there exist two elements in the BST whose sum equals k" (LeetCode 653).

Clarifying questions to ask

Must the two elements be different nodes? (Yes.)
Is extra O(n) memory acceptable? (Then a hash set works; the follow-up asks for O(h).)
Are there duplicates? (No.)

Follow-ups to expect

"Hash-set approach?"
"Why two iterators?"
"When do the pointers stop?"
"Why is it correct to discard values?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview