Two Sum BSTs in Linear Time

Medium-level problem: https://leetcode.com/problems/two-sum-bsts/

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

Constraints:

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

Likely the author is expecting an O(nlogn) solution, but there is a way to do in O(n) if you're willing to spare some extra space:

• Push the items from the first tree (non-recursively) into a Hashtable
• Go thru each item in the second tree looking for Target-Item in the Hashtable

Runs in 120ms. Code is below, cheers, ACC.

public class Solution

{

    public bool TwoSumBSTs(TreeNode root1, TreeNode root2, int target)

    {

        if (root1 == null || root2 == null) return false;

        Hashtable ht = new Hashtable();

        Queue queue = new Queue();

        queue.Enqueue(root1);

        while (queue.Count > 0)

        {

            TreeNode tn = (TreeNode)queue.Dequeue();

            if (!ht.ContainsKey(tn.val)) ht.Add(tn.val, true);

            if (tn.left != null) queue.Enqueue(tn.left);

            if (tn.right != null) queue.Enqueue(tn.right);

        }

        queue.Enqueue(root2);

        while (queue.Count > 0)

        {

            TreeNode tn = (TreeNode)queue.Dequeue();

            if (ht.ContainsKey(target - tn.val)) return true;

            if (tn.left != null) queue.Enqueue(tn.left);

            if (tn.right != null) queue.Enqueue(tn.right);

        }

        return false;

    }

}