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

💡 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