653.md

653. Two Sum IV - Input is a BST

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: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * Traverse the binary tree with Depth-First Search (DFS) algorithm (preorder)
 * meanwhile using binary search tree (BST) to seek targets
 * @param {TreeNode} root
 * @param {number} k
 * @return {boolean}
 */
var findTarget = function(root, k) {
    "use strict";
    /** 
     * Search for the target number in a binary search tree (BST)
     * @param {TreeNode} node: The root of BST
     * @param {number} num: The target number
     * @param {boolean} findTwice: Do we need to find the target twice?
     * @return {boolean}
     */
    function searchTarget(node, num, findTwice) {
        if (!node) {
            return false;
        }
        if (node.val === num) {
            if (findTwice) {
                return (node.left && node.left.val === num) ||
                    (node.right && node.right.val === num);
            } else {
                return true;
            }
        } else if (node.val > num) {
            return searchTarget(node.left, num, findTwice);
        } else {
            return searchTarget(node.right, num, findTwice);
        }
    }
    function dfs(node) {
        if (node) {
            // If two elements happen to be the same
            // then we need to find the target twice during our search
            if (searchTarget(root, k-node.val, k-node.val === node.val)) {
                return true;
            } else {
                return dfs(node.left) || dfs(node.right);
            }
        }
    }
    return dfs(root) ? true : false;
};