Two Sum IV — Input is a BST

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.

Example 1:

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

Approach

This question is similar to finding if their are two elements in an array such that their sum is equal to the given target.

This problem can be solved either using BFS or DFS. We will solve this using level order traversal(BFS) which uses queue data structure for tree traversing.

The idea here is initialize an empty set , for every node check if target-node.value is available in set , if it is available return True , else add that node value to the set.

At the end directly return False as there is no such elements present in BST.

The reason why I have chosen set for storing the node values is , insert and retrieve operations on set can be done in O(1) time complexity as internally set is implemented using Hashing.

Code

from collections import deque
# 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:
        queue = deque()
        queue.append(root)
        available = set()
        while len(queue)>0:
            popped = queue.popleft()
            if k-popped.val in available:
                return True
            else:
                available.add(popped.val)
            if popped.left:
                queue.append(popped.left)
            if popped.right:
                queue.append(popped.right)
        return False

Note: If anyone want to more about level order traversal of a tree , please let me know in comments. I will write a detailed post on level order traversal.