Pair Across Two Search Trees

Medium

You are given the roots first and second of two binary search trees and an integer goal. All values within a tree are distinct: for every node, the values in its left subtree are smaller than its own and the values in its right subtree are larger. Return True if you can pick one node from the first tree and one from the second so that their values add up to goal, and False otherwise.

Example 1

first=tree_node([6, 2, 9]), second=tree_node([4, 1, 8]), goal=10 → True

6 from the first tree plus 4 from the second gives 10.

Example 2

first=tree_node([3, 1, 5]), second=tree_node([20, 10, 30]), goal=12 → False

The possible sums are 11, 13, 15, 21, 23, 25, 31, 33 and 35; 12 is not among them.

Example 3

first=tree_node([-5]), second=tree_node([0, -7, None, None, -2]), goal=-7 → True

Constraints

1 ≤ number of nodes in each tree ≤ 5·10⁴
-10⁹ ≤ Node.val ≤ 10⁹
-10⁹ ≤ goal ≤ 10⁹
Both trees are valid search trees

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Tree Depth-First Search Binary Search Tree Two Pointers Binary Search Binary Tree

Similar problems

K Keys Nearest to a Target Hard Floor and Ceiling in a Search Tree Medium Nearest Value in a Search Tree Easy Pair Sum in a Search Tree Easy Search Tree Into a Line Easy

Input

first=tree_node([6, 2, 9]), second=tree_node([4, 1, 8]), goal=10

Expected

True

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