0653. Two Sum IV - Input is a BST

Easy | Binary Search Tree + Stack | 72 ms (92.85%), 16.6 MB (76.64%)

❓ Problem Statement

Source: LeetCode - Two Sum IV - Input is a BST GitHub: Solution / Performance

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

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].

• -10^4 <= Node.val <= 10^4

• root is guaranteed to be a valid binary search tree.

• -10^5 <= k <= 10^5

💡 Ideas

Using "Stack" to traverse BST and using "Set" to record each node value.

🤖 Python3

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        
        # ==================================================
        #  Binary Search Tree + Stack                      =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        stack = [root]
        values = set()
        
        while stack:
            node = stack.pop()
            if k - node.val in values: return True
            values.add(node.val)
            
            if node.left: stack.append(node.left)
            if node.right: stack.append(node.right)
        
        return False

🤖 Java

class Solution {
    /**  
     * @time  : O(n)
     * @space : O(n)
     */
    
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> values = new HashSet<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(values.contains(k - node.val)) return true;
            values.add(node.val);
            
            if(node.left != null) stack.push(node.left);
            if(node.right != null) stack.push(node.right);
        }
        
        return false;
    }
}