Skills101
← All coding problems

Two Sum in BST

easyTrees & BST II+10 XPTime limit 2s

A binary search tree with distinct values is given, along with a number k. Are there two different nodes whose values add up to exactly k?

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input: one BST, then a line k.

Output: true or false.

Constraints: 1 ≤ nodes ≤ 10⁴, distinct values between −10⁴ and 10⁴, −3·10⁴ ≤ k ≤ 3·10⁴. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: checking every pair is O(n²). Two O(n) ideas: put the values in a hash set while traversing and look for k − value; or take the inorder traversal (it is sorted!) and use two pointers from both ends.

Sample input 1

5 3 6 2 4 null 7
9

Sample output 1

true

Sample input 2

5 3 6 2 4 null 7
28

Sample output 2

false

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.