Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I know there are a few recursive ways to solve this problem but the code below is what came to mind for me.

void create_bst(node *root, vector<int> arr)
{
    int len = arr.size();
    add_nodes(root,len-1); //Make the tree structure
    inorder_traversal(root,arr);
}

void add_nodes(node *n, int len)
{   
queue<node *> bfs;
bfs.push(n);
int i = 1;

    while(!bfs.empty())
    {
    node *temp = bfs.front();
    bfs.pop();

    temp->left = new node(i++);
    len--;
    if(len == 0)
    {
        break;
    }
    bfs.push(temp->left);

    temp->right = new node(i++);
    len--;
    if(len == 0)
    {
        break;
    }
    bfs.push(temp->right);
    }
}

void inorder_traversal(node *n, vector<int> arr)
{
static int i=0;
if(n->left != NULL)
{
    inorder_traversal(n->left,arr);
}
if(n != NULL)
{
    n->data = arr[i];
    i++;
}
if(n->right != NULL)
{
    inorder_traversal(n->right,arr);
}
}

The add nodes function creates the BST and the inorder traversal function inserts the appropriate values at each node. Is the algorithm above an efficient way to solve this problem?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted
  1. Your code will only work one time, because of the static int i in your inorder_traversal function. You have no way to reset i to 0

  2. Splitting creation and filling into two parts is not what I'd call efficient. This way you have to traverse the tree twice: once while creating it and once while filling it. And if you do not depend on a complete binary tree, managing a queue is a wast of time and unnecessary complexity to whom ever is trying to read your code.

My advice would be, work recursive on recursive data. The recursive way is much shorter and much easier to read, isn't it?

node* create_bst(vector<int> const& arr)
{
  return create_bst(arr, 0, arr.size());
}

node* create_bst(vector<int> const& arr, int start, int end)
{
  if (start >= end)
    return null;

  int m = (start + end) / 2;

  node* root = new node(arr[m]);

  root->left = create_bst(arr, start, m);
  root->right = create_bst(arr, m + 1, end);

  return root;
}
share|improve this answer
2  
The only difference I would do is use iterators (and not pass the array). It looks more like standard C++ function then. –  Loki Astari Jan 26 '13 at 22:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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