CODEWITHSUNDEEP
algorithm
SmacL
SmacL

Reputation: 22922

How to build a binary tree in O(N ) time?

Following on from a previous question here I'm keen to know how to build a binary tree from an array of N unsorted large integers in order N time?

Upvotes: 1

Views: 7459

Answers (4)

blazs
blazs

Reputation: 4845

I agree that this seems impossible in general (assuming we have a general, totally ordered set S of N items.) Below is an informal argument where I essentially reduce the building of a BST on S to the problem of sorting S.

Informal argument. Let S be a set of N elements. Now construct a binary search tree T that stores items from S in O(N) time.

Now do an inorder walk of the tree and print values of the leaves as you visit them. You essentially sorted the elements from S. This took you O(|T|) steps, where |T| is the size of the tree (i.e. the number of nodes). (The size of the BST is O(N log N) in the worst case.)

If |T|=o(N log N) then you just solved the general sorting problem in o(N log N) time which is a contradiction.

Upvotes: 1

Matt Timmermans
Matt Timmermans

Reputation: 59174

OK, just for completeness... The binary tree in question is built from an array and has a leaf for every array element. It keeps them in their original index order, not value order, so it doesn't magically let you sort a list in linear time. It also needs to be balanced.

To build such a tree in linear time, you can use a simple recursive algorithm like this (using 0-based indexes):

//build a tree of elements [start, end) in array
//precondition: end > start
buildTree(int[] array, int start, int end)
{
    if (end-start > 1)
    {
        int mid = (start+end)>>1;
        left = buildTree(array, start, mid);
        right = buildTree(array, mid, end);
        return new InternalNode(left,right); 
    }
    else
    {
        return new LeafNode(array[start]);
    }
}

Upvotes: 2

olegarch
olegarch

Reputation: 3891

I have an idea, how it is possible.

Sort array with RadixSort, this is O(N). Thereafter, use recursive procedure to insert into leafs, like:

node *insert(int *array, int size) {
  if(size <= 0)
     return NULL;
  node *rc = new node;
  int midpoint = size / 2;
  rc->data = array[midpoint];
  rc->left  = insert(array, midpoint);
  rc->right = insert(array + midpoint + 1, size - midpoint - 1);
  return rc;
}

Since we do not iterate tree from up to down, but always attach nodes to a current leafs, this is also O(1).

Upvotes: 0

tt9
tt9

Reputation: 6069

Unless you have some pre-conditions on the list that allow you to calculate the position in the tree for each item in constant time it is not possible to 'build', that is sequentially insert, items into a tree in O(N) time. Each insertion has to compare up to Log M times where M is the number of items already in the tree.

Upvotes: 3

Related Questions