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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9};
10
11void inorder(struct TreeNode* root, int* arr, int* size) {
12 if (root == NULL) return;
13 inorder(root->left, arr, size);
14 arr[(*size)++] = root->val;
15 inorder(root->right, arr, size);
16}
17
18bool findTarget(struct TreeNode* root, int k) {
19 int arr[10000]; // reasonable max size
20 int size = 0;
21 inorder(root, arr, &size);
22 int left = 0, right = size - 1;
23 while (left < right) {
24 int sum = arr[left] + arr[right];
25 if (sum == k) {
26 return true;
27 } else if (sum < k) {
28 left++;
29 } else {
30 right--;
31 }
32 }
33 return false;
34}
35This C solution first performs an inorder traversal to convert the BST into a sorted array. With two pointers, it iterates over the array to find if a pair exists that sums up to 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#
This C solution builds upon a hash table for constant time lookups of complements (values such that k - node.val). For brevity, hash table methods are assumed implemented.