Problem statement

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

Solution

Straightforward solution is just traverse our tree and use 1. Two Sum, where we can use hash table to have O(n) time/space complexity. Can we do better? For time - no, but what about space?

We can use the idea of problem 173 Binary Search Tree Iterator to avoid O(n) space. The idea is to use iterators next and prev, which can be written as one iterator get(node, dr), where dr is direction of traverse. Then we start with root, find next and previous elements in inorder traversal, which are the smallest and the biggest elements and use usual 2sum logic with two pointers.

Comlexity

Time complexity is O(n), space complexity is O(h) for implicit recursion stack of our iterators.

Code

class Solution:
    def findTarget(self, root: TreeNode, k):
        def get(node, dr):
            if not node: return
            first, last = (node.left, node.right)[::dr]
            yield from get(first, dr)
            yield node.val
            yield from get(last, dr)
        
        head, tail = get(root, 1), get(root, -1)
        n1, n2 = next(head), next(tail)
        while n1 < n2:
            if n1 + n2 < k: n1 = next(head)
            elif n1 + n2 > k: n2 = next(tail)
            else: return True