I wrote the below code for finding a Triplet in a BST that adds upto 0. But having difficulty determining the time complexity.
The find() method's time complexity is O(logn). Is the time time complexity of isTriplet() O(n^2) ?
bool find(Node* root, int target) {
if (root == NULL)
return false;
if (root->data == target)
return true;
return (target < root->data) ? find(root->left, target) : find(root->right, target);
}
bool isTriplet(Node* root, Node* actualRoot) {
if (root == NULL)
return false;
if (root->left == NULL && root->right == NULL)
return false;
int sum = root->data;
if (root->left)
sum += root->left->data;
else if (root->right)
sum += root->right->data;
sum = -1 * sum;
return (find(actualRoot, sum) || isTriplet(root->left, actualRoot) || isTriplet(root->right, actualRoot));
}
Aucun commentaire:
Enregistrer un commentaire