D
DevExCode

LeetCode 653: Two Sum IV - Input is a BST Solution

Master LeetCode problem 653 (Two Sum IV - Input is a BST), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can perform an in-order traversal of the BST and simultaneously check if there exist two elements in the BST whose sum equals k. We can use a HashSet to keep track of the elements we have seen during the traversal. At each node, we check if k - node.val is present in the set. If it is, then we have found the two elements whose sum equals k. If not, we add the current node's value to the set and continue the traversal.

Algorithm:

  1. Perform in-order traversal of the BST.
  2. At each node, check if k - node.val is in the HashSet.
  3. If it is, return true.
  4. If not, add the current node's value to the HashSet.
  5. Continue the traversal until all nodes are visited.
  6. If no such pair is found, return false.

Time Complexity:

The time complexity of this approach is O(n) where n is the number of nodes in the BST.

Space Complexity:

The space complexity is also O(n) due to the HashSet used to store the values.

:

Solution Code

import java.util.HashSet;

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

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 653 (Two Sum IV - Input is a BST)?

This page provides optimized solutions for LeetCode problem 653 (Two Sum IV - Input is a BST) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 653 (Two Sum IV - Input is a BST)?

The time complexity for LeetCode 653 (Two Sum IV - Input is a BST) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 653 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 653 in Java, C++, or Python.

Back to LeetCode Solutions