two-sum-bsts

< Previous 　　　　　　　　　　　　　　　　 Next >

1214. Two Sum BSTs (Medium)

Given two binary search trees, return True if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

 

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 and 3 sum up to 5.

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

 

Note:

1. Each tree has at most 5000 nodes.
2. -10^9 <= target, node.val <= 10^9

Related Topics

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

Similar Questions

1. Two Sum IV - Input is a BST (Easy)

Hints

Hint 1

How can you reduce this problem to the classical Two Sum problem?

Hint 2

Do an in-order traversal of each tree to convert them to sorted arrays.

Hint 3

Solve the classical Two Sum problem.