Reference: LeetCode
Difficulty: Medium

## Problem

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:

Note:

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

## Analysis

### Brute-Force

Time: $O(MN)$
Space: $O(\max{(M, N)})$

### Two Pointers

Convert to two lists list1 and list2, then apply the two-pointer method.

Time: $O(M + N)$
Space: $O(\log{\max{(M, N)}})$ in the best case; $O(\max{(M, N)})$ in the worst case.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.
Newest Comments
loading...
Info
Article :
50
Total Count :
82.3k
UV :
PV :
Last Push :