[Java/C++] Three simple methods - choose one you like


  • 31

    Method 1.
    This method also works for those who are not BSTs. The idea is to use a hashtable to save the values of the nodes in the BST. Each time when we insert the value of a new node into the hashtable, we check if the hashtable contains k - node.val.

    Time Complexity: O(n), Space Complexity: O(n).

    Java version:

        public boolean findTarget(TreeNode root, int k) {
            HashSet<Integer> set = new HashSet<>();
            return dfs(root, set, k);
        }
        
        public boolean dfs(TreeNode root, HashSet<Integer> set, int k){
            if(root == null)return false;
            if(set.contains(k - root.val))return true;
            set.add(root.val);
            return dfs(root.left, set, k) || dfs(root.right, set, k);
        }
    

    C++ version:

        bool findTarget(TreeNode* root, int k) {
            unordered_set<int> set;
            return dfs(root, set, k);
        }
        
        bool dfs(TreeNode* root, unordered_set<int>& set, int k){
            if(root == NULL)return false;
            if(set.count(k - root->val))return true;
            set.insert(root->val);
            return dfs(root->left, set, k) || dfs(root->right, set, k);
        }
    

    Method 2.
    The idea is to use a sorted array to save the values of the nodes in the BST by using an inorder traversal. Then, we use two pointers which begins from the start and end of the array to find if there is a sum k.

    Time Complexity: O(n), Space Complexity: O(n).

    Java version:

        public boolean findTarget(TreeNode root, int k) {
            List<Integer> nums = new ArrayList<>();
            inorder(root, nums);
            for(int i = 0, j = nums.size()-1; i<j;){
                if(nums.get(i) + nums.get(j) == k)return true;
                if(nums.get(i) + nums.get(j) < k)i++;
                else j--;
            }
            return false;
        }
        
        public void inorder(TreeNode root, List<Integer> nums){
            if(root == null)return;
            inorder(root.left, nums);
            nums.add(root.val);
            inorder(root.right, nums);
        }
    

    C++ version:

        bool findTarget(TreeNode* root, int k) {
            vector<int> nums;
            inorder(root, nums);
            for(int i = 0, j = nums.size()-1; i<j;){
                if(nums[i] + nums[j] == k)return true;
                (nums[i] + nums[j] < k)? i++ : j--;
            }
            return false;
        }
        
        void inorder(TreeNode* root, vector<int>& nums){
            if(root == NULL)return;
            inorder(root->left, nums);
            nums.push_back(root->val);
            inorder(root->right, nums);
        }
    

    Method 3.
    The idea is to use binary search method. For each node, we check if k - node.val exists in this BST.

    Time Complexity: O(nlogn), Space Complexity: O(h). h is the height of the tree, which is logn at best case, and n at worst case.

    Java version:

        public boolean findTarget(TreeNode root, int k) {
            return dfs(root, root,  k);
        }
        
        public boolean dfs(TreeNode root,  TreeNode cur, int k){
            if(cur == null)return false;
            return search(root, cur, k - cur.val) || dfs(root, cur.left, k) || dfs(root, cur.right, k);
        }
        
        public boolean search(TreeNode root, TreeNode cur, int value){
            if(root == null)return false;
            return (root.val == value) && (root != cur) 
                || (root.val < value) && search(root.right, cur, value) 
                    || (root.val > value) && search(root.left, cur, value);
        }
    

    C++ version:

        bool findTarget(TreeNode* root, int k) {
            return dfs(root, root,  k);
        }
        
        bool dfs(TreeNode* root,  TreeNode* cur, int k){
            if(cur == NULL)return false;
            return search(root, cur, k - cur->val) || dfs(root, cur->left, k) || dfs(root, cur->right, k);
        }
        
        bool search(TreeNode* root, TreeNode *cur, int value){
            if(root == NULL)return false;
            return (root->val == value) && (root != cur) 
                || (root->val < value) && search(root->right, cur, value) 
                    || (root->val > value) && search(root->left, cur, value);
        }
    

  • 0

    Hope your advice!


  • 1
    G

    Nice explanation!


  • 0
    M

    @Hao-Cai said in [Java/C++] Three simple methods - choose one you like:

    O(logn).

    Hi, I don't understand why the space complexity is O(logn) for method 3?


  • 0
    Y

    Nice explanation @Hao-Cai. Just one concern, in method 2, don't you think it is unnecessary to pass 'k' in your helper function 'inOrder' as an argument. Let me know if I am missing something.


  • 2
    B

    @manishreddy said in [Java/C++] Three simple methods - choose one you like:

    @Hao-Cai said in [Java/C++] Three simple methods - choose one you like:

    O(logn).

    Hi, I don't understand why the space complexity is O(logn) for method 3?

    I think it is AVERAGE O(logn).
    Worst case still O(n): the depth of the tree is n.


  • 0

    @yash.shrivastav25 Yes, you are right...That's my mistake. I modified it. Thank you very much!


  • 1

    @manishreddy Sry, I think it's my mistake. The space complexity should be O(h), where h is the height of the BST. h chould be between logn and n.


  • 0

    @bluesky2 Yes, you are right. It's my mistake.


  • 0
    L

    Thanks for your sharing,but I have a little doubt. If the k == 8,one of the nodes is only one 4,the result if true or false?


  • 0

    @loveluckystar It should be false.


  • 0
    T

    I think you need to consider overflow in this problem.


  • 0

    @tlj77 thanks for your advice! Can you explain more clearly?


  • 0
    T

    You have (k - root.val), this could cause Integer overflow.


  • 0

    @tlj77 thank you! This is a very good point!


  • 0
    C

    @manishreddy Because the third solution is using recursion which will also add to the space complexity.


  • 0
    S

    @Hao-Cai In your method 1, java version, could you explain why would we need to add the root value back if the set doesn't contain (k-root.val)? Thanks!


  • 0

    @Shayy You need to save the value of each node into map to check.


  • 0
    S

    @Hao-Cai said in [Java/C++] Three simple methods - choose one you like:

    @

    I thought the .contains method already check whether the value is in map?


  • 0

    @Shayy Yes, but if you want to check every value of the tree, you must save each value in map. Is it right?


Log in to reply
 

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