091.md

653. Two Sum IV - Input is a BST

Difficulty: 🟢 Easy

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

Examples:

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 104 <= Node.val <= 104
• root is guaranteed to be a valid binary search tree.
• 105 <= k <= 105

Solutions

O(n) solution with HashSet

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        seen, stack = set(), [root]
        while stack:
            node = stack.pop()
            if k - node.val in seen:
                return True

            seen.add(node.val)
            if node.left:
                stack.append(node.left)

            if node.right:
                stack.append(node.right)
        return False

The given solution provides an approach to find whether there exist two elements in the BST such that their sum is equal to k.

Here is a step-by-step overview of the solution:

1. Initialize an empty set called seen to keep track of visited values in the tree.
2. Initialize a stack and add the root node to it.
3. Iterate through the stack:
   • Pop a node from the stack.
   • Check if k minus the value of the current node is in the set seen. If it is, return True as we found a pair of elements whose sum is equal to k.
   • Add the value of the current node to the set seen.
   • If the left child of the current node exists, push it onto the stack.
   • If the right child of the current node exists, push it onto the stack.

If we don't find any such pair, return False.

Complexity Analysis

The time complexity for this solution is O(n), where n is the number of nodes in the binary tree. In the worst case, we visit each node once.

The space complexity is O(n) in the worst case. This occurs when the tree is skewed and all nodes are pushed onto the stack.

Summary

The given solution provides an approach to determine whether there exist two elements in a binary search tree such that their sum is equal to a given integer k. It uses a set to keep track of visited values and iterates through the tree to check for the sum. The solution has a time complexity of O(n) and a space complexity of O(n), where n is the number of nodes in the binary tree.

O(n) solution without HashSet

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        def find(node, target):
            if not node:
                return None
            if node.val == target:
                return node
            elif node.val < target:
                return find(node.right, target)
            else:
                return find(node.left, target)

        stack = [root]
        while stack:
            node = stack.pop()
            temp = find(root, k-node.val)
            if temp and node is not temp:
                return True

            if node.left:
                stack.append(node.left)

            if node.right:
                stack.append(node.right)
        return False

The given solution provides an approach to find whether there exist two elements in the BST such that their sum is equal to k.

Here is a step-by-step overview of the solution:

1. Define a helper function find that takes a node and a target value and performs a binary search to find a node with the given target value in the BST.
2. Initialize a stack and add the root node to it.
3. Iterate through the stack:
   • Pop a node from the stack.
   • Find the node with the value k minus the value of the current node using the find function.
   • If such a node exists and it's not the current node, return True as we found a pair of elements whose sum is equal to k.
   • If the left child of the current node exists, push it onto the stack.
   • If the right child of the current node exists, push it onto the stack.

If we don't find any such pair, return False.

Complexity Analysis

The time complexity for this solution is O(n log n) in the worst case, where n is the number of nodes in the binary tree. This is because for each node, we perform a binary search using the find function which takes O(log n) time.

The space complexity is O(n) in the worst case. This occurs when the tree is skewed and all nodes are pushed onto the stack.

Summary

The given solution provides an approach to determine whether there exist two elements in a binary search tree such that their sum is equal to a given integer k. It uses a binary search for each node to find a node with the complementary value. The solution has a time complexity of O(n log n) and a space complexity of O(n), where n is the number of nodes in the binary tree.

NB: If you want to get community points please suggest solutions in other languages as merge requests.