3

An algorithm is given on GeeksForGeeks.com for constructing a Binary Search Tree from its preorder traversal.

They say that the time complexity for the following code is O(n^2). But in my opinion it should be O(nlogn). I'm confident about calculating O() for most algorithms, but here there's a divide and conquer algorithm, which runs as T(n) = T(n/2) + O(n), which I believe should be working in O(nlogn) by the master method?

Can someone please tell how the complexity is O(n^2)?

The idea of the code is :

The first element of preorder traversal is always root. We first construct the root. Then we find the index of first element which is greater than root. Let the index be ‘i’. The values between root and ‘i’ will be part of left subtree, and the values between ‘i+1′ and ‘n-1′ will be part of right subtree. Divide given pre[] at index “i” and recur for left and right sub-trees.

For example in {10, 5, 1, 7, 40, 50}, 10 is the first element, so we make it root. Now we look for the first element greater than 10, we find 40.

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

// A utility function to create a node
struct node* newNode (int data)
{
    struct node* temp = (struct node *) malloc( sizeof(struct node) );
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// A recursive function to construct Full from pre[]. preIndex is used
// to keep track of index in pre[].
struct node* constructTreeUtil (int pre[], int* preIndex,
                            int low, int high, int size)
{
    // Base case
    if (*preIndex >= size || low > high)
        return NULL;

    // The first node in preorder traversal is root. So take the node at
    // preIndex from p re[] and make it root, and increment preIndex
    struct node* root = newNode ( pre[*preIndex] );
    *preIndex = *preIndex + 1;

        // If the current subarry has only one element, no need to recur
    if (low == high)
        return root;

    // Search for the first element greater than root
    int i;
    for ( i = low; i <= high; ++i )
        if ( pre[ i ] > root->data )
            break;

    // Use the index of element found in postorder to divide postorder array in
    // two parts. Left subtree and right subtree
    root->left = constructTreeUtil ( pre, preIndex, *preIndex, i - 1, size );
    root->right = constructTreeUtil ( pre, preIndex, i, high, size );

    return root;
}

// The main function to construct BST from given preorder traversal.
// This function mainly uses constructTreeUtil()
struct node *constructTree (int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil (pre, &preIndex, 0, size - 1, size);
}
  • 1
  • @gnat, I'm confident about calculating O() for most algorithms, but here there's a divide and conquer algorithm, which runs as T(n) = T(n/2) + O(n), which in my opinion should be working in O(nlogn) by the master method? – Dhruv Mullick Jul 23 '15 at 21:55
  • Could they have mentioned that complexity keeping the worst case in mind? Normally when you see quicksort, for example, they mention that O(nlogn) is the average case complexity - and it would be O(n^2) in worst case. – Mehdi Maujood Jul 23 '15 at 22:40
  • O(n log n) is in O(n^2), so I don't see any contradiction here. (Note: I haven't checked the math, to verify that the algorithm actually is in O(n log n), but even assuming that it is, it is still also on O(n^2).) – Jörg W Mittag Jul 23 '15 at 22:42
2

While the stated algorithm is O(n log n) on the average case, it is O(n^2) in the worst case, i.e. when used to reconstruct a tree in which each node has an empty branch either to its left or right. Such a tree has a depth of n, and therefore the algorithm will recurse n times, each recursion requiring an average of n/2 comparisons to complete.

  • Do you think it would be a good idea to use this algorithm if an interviewer says that he wants a solution with O(nlogn) complexity? – Dhruv Mullick Jul 24 '15 at 7:02
  • @DhruvMullick ask them if they want worst case O(n log n), or if they'd be happy with average O(n log n) / worst-case O(n^2). The latter describes quicksort, for example, which people tend to think of as suitable for general use. – AakashM Jul 24 '15 at 13:26
  • It's certainly worth noting that depending on the source of the data it may be impossible to ever actually see a non-trivial example of the worst case. For example, if the tree being built is known to have been produced by a standard balanced tree generation method (e.g. red/black tree) then you can guarantee O(n log n). – Jules Jul 24 '15 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.