Given a sorted array in increasing order, create a BST of minimum height

Question

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?

Answer 1

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;
}