Did I manage to estimate O(n) correctly?

Question

Please note: this question not about the best implementation of algorithm, neither about datastructures.

Given a binary tree, it is required to verify that it is a bst. I am aware about much more efficient (O(n)) algorithm, the question is not about it. I am practicing my big-O-estimation skills:

int isBST(struct node* node)  
{  
  if (node == NULL)  
    return(true);  

  if (node->left!=NULL && maxValue(node->left) > node->data)  
    return(false);  

  if (node->right!=NULL && minValue(node->right) < node->data)  
    return(false);  

  if (!isBST(node->left) || !isBST(node->right))  
    return(false);  

  return(true);  
}

..assuming that maxValue(...)/minValue(...) are helper functions that each takes O(n) to run.

If h is the number of "levels" it has starting from the root and ending up with leaves. At each level both maxValue(...) and minValue(...) are called on the (n - 1) / 2^l range, where l is the current level. There are h levels, so I expect to get something like (n - 1) / 1 + (n - 1) / 2 + (n - 1) / 4 + ... + (n - 1) / 2^h. So it seems like O(n * h) is a correct upper bound, is it?

Please verify my way of thinking.

In one extreme, a linked list is actually a binary search tree which is maximally unbalanced, and has all children in one direction. So, verifying that a data structure is a binary search tree is not necessarily a meaningful thing. — Tim Biegeleisen, Mar 17 '19 at 15:27
@TimBiegeleisen, thanks. I do understand it. I am fine with trees and operations on it, the only thing I leak is good `O(n)` estimation skills for recursive stuff. That's the only purpose I've wrote this question. — Zazaeil, Mar 17 '19 at 15:31
@melpomene, got rid of the 'height' to avoid confusion. Please see updates. — Zazaeil, Mar 17 '19 at 15:34
The `minvalue()` and `maxvalue()` functions are called for every node, and visit the entire subree(s) .So, the complexity **must** be > O(N). [for demonstration purposes, you could add three (global) visitcounters to the three functions, and play with it] — wildplasser, Mar 17 '19 at 16:08
@wildplasser, it is actually `n * log_2(n)` for balanced trees, AFAICS. 'Cause `h` is number of levels particular (balanced) tree has, so it is function of `n` as well rather than constant. — Zazaeil, Mar 17 '19 at 16:15
So, it will be O(N*N) for the pathological linked-list worst case. — wildplasser, Mar 17 '19 at 16:21
@wildplasser, not quite. I bet there is a tigher versions, since `O(n * n)` does not take into consideration gradual decresing of `n` as you go from the top to the bottom of a tree. — Zazaeil, Mar 17 '19 at 16:24

Javier Cano · Accepted Answer · 2019-03-18T20:37:50.510

Yes, you are correct. That's the right upper bound. At each level you will do overall O(n) work for the maxValues. You can check this for a very similar run-time analysis (it gives O(nlogn) since h = logn as the assumption is it is well balanced). Using h is a good call, if the tree is completely unbalance (h = O(n)) then the runtime will be O(n^2) but if it is perfectly balanced (h= O(logn)) you will have O(nlogn).

One more thing, you can actually cache/calculate the max/min values while recursing, it will give you an amortized O(n) runtime:

struct helper {
  int min;
  int max;
};

int isBST(struct node* root) {  
  struct helper help;
  return isBST_internal(root, &help);  
}

int isBST_internal(struct node* root, struct helper *min_max) {
  if (!root) return true;

  if (root->left) {
    // Recurse on left
    struct helper left_helper;
    int is_left_BST = isBST_internal(root->left, &left_helper)

    if (!is_left_BST || left_helper.max > root->data)
      return false;

    min_max->min = left_helper.min;
  } else {
    // If no left subtree, the min value should be the current node value
    min_max->min = root->data;
  }

  if (root->right) {
    // recurse on right side
    struct helper right_helper;
    int is_right_BST = isBST_internal(root->right, &right_helper)

    if (!is_right_BST || right_helper.min < root->data)
      return false;

    min_max->max = left_helper.max;
  } else {
    // If no right subtree, the max value should be the current node value
    min_max->max = root->data;
  }

  // If we have not returned yet it means all conditions for BST are satisfied
  // Also, min_max is properly set now.

  return true
}

It may not be the cleanest solution, but certainly will run on linear time. With an extra O(h) space penalty, (to hold the helper structs on the function stack), but still, such overhead is normal while recursing anyway.

Did I manage to estimate O(n) correctly?

1 Answers1