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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Two Sum IV - Input is a BST

Difficulty: Easy

Problem Description

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.

Key Insights

  • A Binary Search Tree (BST) allows for efficient searching, inserting, and deleting of nodes.
  • The problem can be efficiently solved using a hash table to keep track of the values we have seen so far.
  • We can traverse the tree using either Depth-First Search (DFS) or Breadth-First Search (BFS) to explore each node.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the BST, since we may need to visit each node once. Space Complexity: O(n), for storing the values in the hash table.

Solution

We can solve this problem using a hash table to store the values of the nodes we encounter during our traversal of the BST. For each node, we check if the complement (k - node.val) exists in the hash table. If it does, we return true. If we finish the traversal without finding such a pair, we return false. This approach utilizes the properties of the BST and ensures we check all necessary values in an efficient manner.

Code Solutions

def findTarget(root, k):
    def dfs(node, seen):
        if not node:
            return False
        if k - node.val in seen:
            return True
        seen.add(node.val)
        return dfs(node.left, seen) or dfs(node.right, seen)

    return dfs(root, set())
← Back to All Questions