Convert Sorted Array to Height Balanced Binary Search Tree

Question

Algorithm

This is my code to convert a sorted vector of integers to a balanced binary tree of the same content.

The binary tree is made of these nodes:

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

Here's my first attempt:

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.empty()) return NULL;
        if(nums.size()==1){
            TreeNode* root = new TreeNode(nums[0]);
            return root;
        }

        int mid = nums.size() / 2;
        TreeNode* root = new TreeNode(nums[mid]);

        vector<int> left(nums.begin(),nums.begin()+mid);
        vector<int> right(nums.begin()+mid+1,nums.end());

        root->left = sortedArrayToBST(left);
        root->right = sortedArrayToBST(right);

        return root;
    }
};

I was making new vectors and copying contents twice in every recursive call, So this is the optimized version by directly passing iterator instead of passing index and copying sub arrays every time:

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
      return makeBST(nums.begin(),nums.end());
    }

    TreeNode* makeBST(vector<int>::iterator start,vector<int>::iterator end){
        if( start >= end ) return NULL;
        vector<int>::iterator mid = start + (end - start) / 2;
        TreeNode* root = new TreeNode(*mid);
        root -> left = makeBST( start , mid );
        root -> right = makeBST( mid + 1 , end );
        return root;
    }
};

The second code has much faster run time than first one.

Is there a better way to pass iterators to function?

Any other improvements?

Answer 1

A class Solution with only public members can be written struct Solution. But with only a single member function (that never uses the this pointer), why not a free function?

Presumably your vector is intended to be a std::vector, in which case we need #include <vector> and the correct namespace qualifier.

Don't pass a reference to a mutable object unless it's reasonable for the function to modify it. In this case, we just want to copy from it, so pass a const std::vector<int>& instead.

You're right that it's very inefficient to make many new containers, when we just want a view; that's exactly what iterator-pairs (aka ranges) are good for. I'll not consider the first version any further.

There's no need to accept only vectors of int - we'd like to accept any ordered random-access container, of any element type. That's easy enough, with a template:

template<typename RandomAccessIterator>
TreeNode* makeBST(RandomAccessIterator start, RandomAccessIterator end){

There's a serious bug when new TreeNode() fails: all the allocated nodes further up the call tree will be leaked as the std::bad_alloc propagates upwards. It's better to make the BST use smart pointers. If you can't change that implementation, then we can achieve exception safety by holding each root in a smart pointer until after the potentially-throwing recursive calls:

    auto root = std::make_unique<TreeNode>(*mid);
    root->left = makeBST(start, mid);
    root->right = makeBST(mid + 1, end);
    return root.release();