# 5 Best Ways to Check if a Triplet with Given Sum Exists in BST in Python

Rate this post

π‘ Problem Formulation: Suppose you are working with a Binary Search Tree (BST) in Python, and you are tasked with determining if there is a triplet of nodes in the tree whose values sum up to a given number. For instance, if your BST contains the numbers [1, 2, 3, 4, 5, 6, 7] and the target sum is 10, you want a method that will confirm the presence of a triplet like (1, 3, 6) in the tree.

## Method 1: Brute Force

This approach involves checking all possible triplets in the BST to find a combination that sums up to the target value. While not efficient for large trees due to its O(N^3) time complexity, it’s a straightforward method to understand and implement.

Here’s an example:

```def find_triplet(root, target):
# Convert BST to sorted list
def inorder(node, elements):
if node is None:
return
inorder(node.left, elements)
elements.append(node.val)
inorder(node.right, elements)

elements = []
inorder(root, elements)

# Check for triplet in sorted list
for i in range(len(elements)):
for j in range(i + 1, len(elements)):
for k in range(j + 1, len(elements)):
if elements[i] + elements[j] + elements[k] == target:
return True
return False
```

Output:

`True or False, depending on the presence of the triplet sum.`

In this example, the `find_triplet` function first converts the BST to a sorted list using the `inorder` function. It then iterates through all possible triplet combinations to find a match for the given sum. It returns `True` if such a triplet exists or `False` otherwise.

## Method 2: Hash Table

To optimize the search, a hash table can be used to store elements that are encountered during traversal. This can reduce the time complexity significantly by allowing us to check for the existence of the third element in constant time.

Here’s an example:

```def is_present_with_sum(root, sum, hash_table):
if not root:
return False
if is_present_with_sum(root.left, sum, hash_table):
return True
if sum - root.val in hash_table:
return True
return is_present_with_sum(root.right, sum, hash_table)

def find_triplet(root, target):
elements = []
inorder(root, elements)
for i in range(len(elements)):
if is_present_with_sum(root, target - elements[i], set()):
return True
return False
```

Output:

`True or False, depending on the presence of the triplet sum.`

The `is_present_with_sum` helper function recursively verifies if there are two elements in the tree that add up to `sum - root.val`, leveraging a hash table for fast lookups. The `find_triplet` function iterates through each element, invoking `is_present_with_sum` to check for the complementary sum needed to form the target triplet sum.

## Method 3: Two Pointers Technique

The two-pointers technique is an efficient way to find pairs in a sorted array that sum to a specific target. This technique can be extended to a BST by converting the BST into a sorted array and then using two pointers to find the triplet.

Here’s an example:

```def find_two_elements_with_sum(elements, target, idx):
left, right = 0, len(elements) - 1
while left < right:
if left == idx:
left += 1
elif right == idx:
right -= 1
current_sum = elements[left] + elements[right]
if current_sum == target:
return True
if current_sum < target:
left += 1
else:
right -= 1
return False

def find_triplet(root, target):
elements = []
inorder(root, elements)
for i in range(len(elements)):
if find_two_elements_with_sum(elements, target - elements[i], i):
return True
return False
```

Output:

`True or False, depending on the presence of the triplet sum.`

The `find_triplet` function uses the `find_two_elements_with_sum` function, which applies the two-pointers technique to a sorted array of BST elements, ignoring the current index `idx`, to find if a pair exists that sums to `target - elements[i]`.

## Method 4: Iterative Deepening

Iterative deepening combines the advantages of breadth-first search’s completeness and depth-first search’s space efficiency. In the context of a BST, it can be used to iteratively explore deeper levels to search for node triplets that match the target sum.

Here’s an example:

```def find_triplet_with_iterative_deepening(root, target):
# Similar code to methods 1-3 for iterative deepening
pass
```

Output:

`Code and output to be added once specific implementation details are known.`

This method is mentioned as a placeholder for a deeper dive. Actual implementation would involve defining a depth limit and performing a depth-first search up to that limit, iterating through combinations of three nodes, and checking their sum against the target.

## Bonus One-Liner Method 5: Using itertools.combinations

This method uses Python’s powerful `itertools` module to generate all possible combinations of tree elements and checks if any triplet sums to the given value. Although concise, it is not recommended for large trees due to computational inefficiency.

Here’s an example:

```from itertools import combinations

def find_triplet(root, target):
elements = inorder_to_list(root)  # Assume this function converts BST to list
return any(sum(triplet) == target for triplet in combinations(elements, 3))

# Code to convert BST to sorted list not shown due to similarity with previous snippets
```

Output:

`True or False, based on the presence of the triplet sum.`

In this concise approach, the function `find_triplet` uses a generator expression within a call to `any()` to determine if a triplet with the target sum exists. We assume the existence of a helper function `inorder_to_list` that we previously defined.

## Summary/Discussion

• Method 1: Brute Force. Simple and straightforward. Very inefficient for large trees.
• Method 2: Hash Table. Faster than the brute force method. Still, it may not be the optimal solution for all cases.
• Method 3: Two Pointers Technique. Very efficient on sorted data. Requires the BST to be converted to a list.
• Method 4: Iterative Deepening. Combines benefits of DFS and BFS. Details not explored in this summary.
• Method 5: Using itertools.combinations. Extremely concise. Inefficient for large datasets.