Two simple elegant approaches in JavaScript. O(n) time O(n) space


  • 3

    Approach 1

    Keep a set of existing values and check for the complement value as you traverse the BST.

    var findTarget = function(root, k) {
        const values = new Set();
        let found = false;
        function inorder(node) {
            if (!node) {
                return;
            }
            inorder(node.left);
            if (values.has(k - node.val)) {
                found = true;
                return;
            }
            values.add(node.val);
            inorder(node.right);
        }
        inorder(root);
        return found;
    };
    

    Approach 2

    This problem can be solved by composing two steps:

    1. Collect all values into a sorted list.
    2. You have just reduced the problem into a Two Sum problem on a sorted list, simply use any of the methods proposed here. In my case I opted for a two pointer approach.
    var findTarget = function(root, k) {
        const values = [];
        function inorder(node) {
            if (!node) {
                return;
            }
            inorder(node.left);
            values.push(node.val);
            inorder(node.right);
        }
        inorder(root);
        let start = 0, end = values.length - 1;
        while (start < end) {
            const total = values[start] + values[end];
            if (total > k) {
                end--;
            } else if (total < k) {
                start++;
            } else {
                return true;
            }
        }
        return false;
    };
    

  • 0
    T

    I used a 3rd approach. Higher time complexity, but O(1) space complexity since we store nothing:

    var findTarget = function(root, k, node, ignoreNode) {
        if (node === undefined) {
            node = root
        }
        
        return !!node && (
            (ignoreNode && node !== ignoreNode && node.val === k) ||
            findTarget(root, k, node.left, ignoreNode) || findTarget(root, k, node.right, ignoreNode) ||
            (!ignoreNode && findTarget(root, k - node.val, root, node))
        )
    };
    

    Short explanation: For each node, we search a second node that will add to k. The first line of the return is used to check if the addition of the two different nodes is equal to k. The second line is for the recursive parse of the tree (for both the first parse and the addition parse). The third line call the addition parse for the current node only if we're not already in an addition parse.
    I think the time comlexity is O(n²) and could be optimize to O(n log(n)) since we're in a BST.


  • 1

    @Thagor Your approach is O(n) space as well. Recursion uses stack space and if the tree is a skewed tree the height of the tree/stack is O(n).


  • 0
    T

    Ok, good to know. Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.