We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Two Sum IV - Input is a BST

Number: 653

Difficulty: Easy

Paid? No

Companies: Amazon, Google, Meta, Goldman Sachs, Microsoft, Apple, Adobe, Oracle, Samsung

Problem Description

Given the root of a binary search tree and an integer k, determine if there exist two different nodes in the BST such that their values add up to k.

Key Insights

  • Utilize the BST property to traverse the tree while checking for the complementary value (k - current node's value).
  • A hash set can be used to store seen node values which facilitates constant time lookups.
  • Alternatively, an in-order traversal converts the BST into a sorted array, allowing a two-pointer approach.
  • The recursive DFS solution is both intuitive and easy to implement for this problem.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes, since each node is visited once. Space Complexity: O(n) in the worst case due to the extra space used by the hash set (or recursion stack in the worst-case scenario of an unbalanced tree).

Solution

The solution uses a depth-first search (DFS) traversal while maintaining a hash set to remember the values of visited nodes. For each node, check if k minus the node's value exists in the hash set. If it does, return true. Otherwise, add the node's value to the set and continue the DFS on both the left and right children. This approach efficiently finds a pair of nodes that sum up to k without needing to traverse the tree more than once.

Code Solutions

# 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: TreeNode, k: int) -> bool:
        seen = set()  # Set to store the values of visited nodes

        def dfs(node):
            if not node:  # Base case: if the node is null, return False
                return False
            # Check if the complement of the current node's value exists in the set
            if (k - node.val) in seen:
                return True
            # Add the current node's value to the set
            seen.add(node.val)
            # Continue DFS traversal on left and right children
            return dfs(node.left) or dfs(node.right)

        return dfs(root)  # Start DFS from the root node
← Back to All Questions