Sponsored
Sponsored
This approach leverages the properties of a Binary Search Tree (BST). By performing an inorder traversal on a BST, we can obtain a sorted list of its elements. Once we have this sorted list, the problem reduces to finding two distinct numbers in this sorted array that sum up to the given target, k. This can efficiently be solved using the two-pointer technique.
Time Complexity: Perform O(n) for traversal and O(n) for two-pointer scan, hence O(n).
Space Complexity: O(n) to store the elements of the tree.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def findTarget(self, root: TreeNode, k: int) -> bool:
9 nums = []
10 self.inorder(root, nums)
11 l, r = 0, len(nums) - 1
12 while l < r:
13 s = nums[l] + nums[r]
14 if s == k:
15 return True
16 elif s < k:
17 l += 1
18 else:
19 r -= 1
20 return False
21
22 def inorder(self, node, nums):
23 if not node:
24 return
25 self.inorder(node.left, nums)
26 nums.append(node.val)
27 self.inorder(node.right, nums)
28The Python solution records values via an inorder traversal. A two-pointer search checks whether any two values sum up to the target k.
This approach utilizes a hash set to store visited node values. We traverse the BST and for each node, check if k - node.val exists in the hash set. If it does, then a pair adding to k has been found.
Time Complexity: O(n), with a pass through each node.
Space Complexity: O(n) for storing nodes in the hash table.
1#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool findTarget(TreeNode* root, int k) {
std::unordered_set<int> set;
return find(root, k, set);
}
bool find(TreeNode* node, int k, std::unordered_set<int>& set) {
if (!node) return false;
if (set.find(k - node->val) != set.end()) return true;
set.insert(node->val);
return find(node->left, k, set) || find(node->right, k, set);
}
Utilizing the unique lookup capability of hash sets in C++, this solution tracks visited complements, early terminating if a match for k is found.