Description

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input:

tree

Target = 9

Output: True

Example 2:

Input:

tree

Target = 28

Output: False

Solution

Inorder traversal, time O(n), space O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        // serialize BST to a sorted list
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int i = 0;
        int j = list.size() - 1;
        
        // 2 sum in sorted list
        while (i < j) {
            int sum = list.get(i) + list.get(j);
            
            if (k == sum) {
                return true;
            } else if (k < sum) {
                --j;
            } else {
                ++i;
            }
        }
        
        return false;
    }
    
    public void inorder(TreeNode t, List<Integer> list) {
        if (t == null) {
            return;
        }
        
        inorder(t.left, list);
        list.add(t.val);
        inorder(t.right, list);
    }
}

DFS & Binary Search, time O(nlogn), space O(h)

h: best is logn, worst is n

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, root, k);
    }
    
    public boolean dfs(TreeNode curr, TreeNode root, int k) {
        if (curr == null) {
            return false;
        }
        
        return binarySearch(curr, root, k - curr.val)
            || dfs(curr.left, root, k)
            || dfs(curr.right, root, k);
    }
    
    public boolean binarySearch(TreeNode curr, TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        
        return (root.val == k && root != curr)  // don't forget root != curr
            || (root.val < k && binarySearch(curr, root.right, k))
            || (root.val > k && binarySearch(curr, root.left, k));
    }
}