Tuesday, February 17, 2015

Google Question: Construct BST from given preorder traversal

Problem: Construct BST from given preorder traversal.

Implementation:

BSTree::BSTree(int *pre, int size)
{
       int index = 0;
       root = constructTree(pre, index, pre[index], INT_MIN, INT_MAX, size);
}

BNode* BSTree::constructTree(int *pre, int &index, int num, int min, int max, int size)
{
     if(index >= size)
              return NULL;
     BNode *node = 0;
     if(num > min && num < max)
     {
            node = new BNode(num);
            ++index;
            if(index < size)
            {
                     node->left =  constructTree(pre, index, pre[index], min, num, size);
                     node->right = constructTree(pre, index, pre[index], num, max, size);
            }
     }
     return node;
}

No comments:

Post a Comment