Find Target Sum in BST
In financial systems, data is often organized in efficient, searchable structures. Imagine a scenario where transaction records or user scores are stored in a Binary Search Tree (BST) to maintain sorted order and enable quick lookups. Your task is to implement a feature that helps identify if any two distinct records (represented by node values) in such a BST sum up to a specific target value. This capability can be crucial for detecting unusual financial patterns or validating data integrity.
Implement the function findTarget which takes the root of a Binary Search Tree and an integer k. Your goal is to determine if there exist two distinct nodes in the tree whose values sum up to k.
Input:
root: The root node of a Binary Search Tree. Each TreeNode has an integer val and references to its left and right children. If the tree is empty, root will be null.k: An integer representing the target sum.Output:
boolean value: true if two distinct nodes with values summing to k are found, false otherwise.k/2.root is null, there are no nodes to form a sum, so the function should return false.root always points to a valid Binary Search Tree (BST). This means for any node, all values in its left subtree are less than its value, and all values in its right subtree are greater than its value. There are no duplicate values in the BST.Examples
Example 1
Input:
root = [5,3,6,2,4,null,7], k = 9
Output:
true
Note:
Nodes 2 and 7 sum to 9. Other pairs like 3+6 also work.
Example 2
Input:
root = [5,3,6,2,4,null,7], k = 28
Output:
false
Note:
No two nodes in the tree sum up to 28.
Example 3
Input:
root = [2,1,3], k = 4
Output:
true
Note:
Nodes 1 and 3 sum to 4.
Example 4
Input:
root = [1], k = 2
Output:
false
Note:
Only one node exists. Two distinct nodes are required.
Constraints
[0, 10^4].[-10^5, 10^5].k is in the range [-10^5, 10^5].Loading editor...