โ† Adobe questions
CodingReported in a candidate post, Jul 2025

Find two elements in a BST that sum to k

Filed under Adobe

Free read 1 of 3

Ask 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

  1. Ask whether the two nodes must be different (yes), whether to return values or nodes, and about duplicates. Note the tree may be unbalanced.

Solution

O(n) time, O(n) space

Python
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.