Find two elements in a BST that sum to k
Filed under Adobe
Free read 1 of 3Ask whether the two nodes must be different (yes), whether to return values or nodes, and about duplicates. Note the tree may be unbalanced.
The question
Given the root of a binary search tree and an integer k, find two different nodes whose values sum to k. Return the pair of values, or None if no such pair exists.
Constraints
- 1 <= number of nodes <= 10^5
- Values are distinct (a BST) and may be negative
- Prefer O(n) time
Examples
- Input
- BST 5(3(2,4),6(null,7)), k = 9
- Output
- (2, 7)
- Why
- 2 + 7 = 9.
- Input
- same BST, k = 28
- Output
- None
- Why
- No two values sum to 28.
Approach
Ask whether the two nodes must be different (yes), whether to return values or nodes, and about duplicates. Note the tree may be unbalanced.
For each node search the tree for k - value: O(n h), up to O(n^2) for a skewed tree. Or a hash set during any traversal: O(n) time, O(n) space.
An inorder traversal of a BST is sorted. Collect it, then move pointers i from the left and j from the right: if the sum is smaller than k advance i, if larger decrement j. O(n) time, O(n) space.
Use two iterators (forward inorder and reverse inorder) with stacks for O(h) space. Edge cases: single node (no pair), same value would be needed twice, negative values, skewed tree (use iteration to avoid deep recursion).
Solution
O(n) time, O(n) space
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
def find_target_bst(root, k):
vals = []
def inorder(n): # inorder of a BST is sorted
if n:
inorder(n.left)
vals.append(n.val)
inorder(n.right)
inorder(root)
i, j = 0, len(vals) - 1
while i < j: # two pointers on the sorted list
s = vals[i] + vals[j]
if s == k:
return (vals[i], vals[j])
i, j = (i + 1, j) if s < k else (i, j - 1)
return None
Tips
- What they are testing: Using the BST property: inorder traversal gives a sorted list, which turns the problem into two-sum on a sorted array.
- Common mistake: Treating it like an unsorted tree and doing nested traversals (O(n^2) or O(n log n)), or using the same node twice (k = 2 x value).
Related Adobe questions
Collected from public candidate posts and coding forums. Updated Nov 2026.