Two Keys That Add Up

EasyTrees

Problem

A binary search tree stores distinct integers. Decide whether two different nodes hold values that add up to target.

Return true or false.

Example 1

Input:
root = [5, 3, 6, 2, 4, null, 7], target = 9
Output:
true

2 + 7, 3 + 6 and 4 + 5 all work.

Example 2

Input:
root = [5, 3, 6, 2, 4, null, 7], target = 28
Output:
false

Constraints

  • 1 ≤ number of nodes ≤ 10^4
  • -10^4 ≤ node.val ≤ 10^4
  • -10^5 ≤ target ≤ 10^5

Hint

Show the first hint

What would you do if the values were in a sorted array?

Walkthrough

How to approach it

01Clarify before coding

  • Can a node pair with itself? No: two different nodes (for example a single 1 does not reach target 2).
  • Are values distinct? Yes.
  • Is the tree balanced? Not necessarily.

02Brute force

For every node, search the tree for target - node.val (and make sure it is a different node).

Cost: O(n·h) time: O(n log n) when balanced but O(n²) for a chain.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.