Pair Sum in a Search Tree

Easy

You are given the root of a binary search tree: for every node, all values in its left subtree are smaller than its value and all values in its right subtree are larger. All values in the tree are distinct. Check whether the tree has two different nodes whose values add up to goal. Return True if such a pair exists, otherwise False.

Example 1

root=tree_node([10, 4, 15, 1, 7, None, 20]), goal=22 → True

7 + 15 = 22, and both values are in the tree.

Example 2

root=tree_node([10, 4, 15, 1, 7, None, 20]), goal=20 → False

20 = 10 + 10, but there is only one node with value 10 and a node cannot be used twice. No other pair works.

Example 3

root=tree_node([3]), goal=6 → False

Constraints

1 ≤ number of nodes ≤ 10⁴
-10⁴ ≤ Node.val ≤ 10⁴
root is a valid binary search tree
-10⁵ ≤ goal ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Binary Search Tree Hash Table Two Pointers Binary Tree

Similar problems

Closest Pair in a Search Tree Easy K Keys Nearest to a Target Hard Tree Columns, Top Down Medium Smallest Cover of the Bottom Row Medium Tree Columns With Ties Hard

Input

root=tree_node([10, 4, 15, 1, 7, None, 20]), goal=22

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.