Frontend School

Find Target Sum in BST

DSA
medium

Find Target Sum in BST

Medium
Tree
Binary Search Tree
DFS
Two Pointers
Hash Table

Overview

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.

What you need to do / Task

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 & output

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:

  • Return a boolean value: true if two distinct nodes with values summing to k are found, false otherwise.

Clarifications

  • Distinct Nodes: The two nodes must be different nodes in the tree. You cannot use the same node twice, even if its value is k/2.
  • Empty Tree: If root is null, there are no nodes to form a sum, so the function should return false.
  • Node Values: Node values can be positive, negative, or zero.
  • Tree Structure: The input 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

1

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.

2

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.

3

Example 3

Input:

root = [2,1,3], k = 4

Output:

true

Note:

Nodes 1 and 3 sum to 4.

4

Example 4

Input:

root = [1], k = 2

Output:

false

Note:

Only one node exists. Two distinct nodes are required.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is in the range [0, 10^4].
  • Node values are in the range [-10^5, 10^5].
  • k is in the range [-10^5, 10^5].
  • The tree is guaranteed to be a valid Binary Search Tree.
  • Node values are unique within the tree.

Out of scope

  • Modifying the structure of the BST.
  • Handling non-integer node values or target sum.
  • Validating if the input tree is indeed a BST (it's guaranteed).

What interviewers evaluate

  • Correctness: The solution accurately identifies if a target sum exists for all valid inputs and edge cases.
  • Efficiency: The solution demonstrates optimal time and space complexity for the given constraints.
  • Clarity & Structure: The code is well-organized, readable, and follows good programming practices.
  • Problem-Solving: Ability to leverage BST properties to simplify the problem and apply appropriate algorithms.

Loading editor...