Leetcode – Two Sum IV – Input is a BST Solution in Python

Spread the love

Introduction

Binary Search Trees (BSTs) are a widely-used data structure in computer science. They allow efficient storage, retrieval, and deletion of data in a sorted manner. In this article, we are going to delve into solving the “Two Sum IV – Input is a BST” problem from Leetcode. This problem combines the concept of the Two Sum problem with the properties of a Binary Search Tree. We will explore the problem in detail, discuss various approaches for solving it, and provide Python code for each solution.

Problem Statement

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:

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

Output: true

Explanation: The BST is:

    5
   / \
  3   6
 / \   \
2   4   7

5 + 4 = 9, so return true.

Note:

  • The number of nodes in the tree is in the range [1, 10^4].
  • -10^4 <= Node.val <= 10^4
  • root is guaranteed to be a valid binary search tree.
  • -10^5 <= k <= 10^5

Solution

1. In-Order Traversal and Two Pointers

One way to approach this problem is to use an in-order traversal to retrieve the elements of the BST in ascending order. Once we have the elements in sorted order, we can use the two-pointer technique to check for two elements whose sum equals the target k.

  1. Perform an in-order traversal to get the elements in ascending order.
  2. Use two pointers, one at the beginning and one at the end of the array.
  3. Move the pointers inward until they meet, checking if the sum of the elements they point to is equal to k.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def find_target(self, root, k):
        def in_order_traversal(node):
            if not node:
                return []
            return in_order_traversal(node.left) + [node.val] + in_order_traversal(node.right)
        
        elements = in_order_traversal(root)
        left, right = 0, len(elements) - 1
        
        while left < right:
            current_sum = elements[left] + elements[right]
            if current_sum == k:
                return True
            elif current_sum < k:
                left += 1
            else:
                right -= 1
        
        return False

Time Complexity:

  • O(n), where n is the number of nodes in the BST.

Space Complexity:

  • O(n), due to storing the elements of the BST in an array.

2. Using a Hash Set

We can solve this problem in a single pass through the BST using a hash set. During the traversal, for each node, we check if the difference between the target value k and the current node’s value is in the hash set. If it is, we have found two elements that add up to k.

  1. Perform any tree traversal (in-order, pre-order, post-order).
  2. For each node, check if k - node.val is in the hash set.
  3. If not, add node.val to the hash set.
class Solution:
    def find_target(self, root, k):
        def dfs(node, seen):
            if not node:
                return False
            complement = k - node.val
            if complement in seen:
                return True
            seen.add(node.val)
            return dfs(node.left, seen) or dfs(node.right, seen)
        
        return dfs(root, set())

Time Complexity:

  • O(n), where n is the number of nodes in the BST.

Space Complexity:

  • O(n), due to storing the elements in a hash set.

Conclusion

In this article, we explored the “Two Sum IV – Input is a BST” problem on Leetcode and discussed two different approaches in Python: In-Order Traversal with Two Pointers and Hash Set. While both solutions have the same time and space complexity, the Hash Set approach is arguably more concise and requires only a single pass through the BST.

Leave a Reply