jeudi 28 juillet 2016

Find a triplet with sum=0 in a BST - Time complexity with below code

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