Given a sorted array, write an algorithm to create a binary search tree with minimal height.


  • 5
    J

    Given a sorted array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

    Input Array = {3,4,5,6,7,8,9,10,12,13}
    Expected Output = {7,4,3,5,6,10,8,9,12,13}

    Logic:

    • Find middle of element in given array and add to Tree.
    • Recursively call makeBSTfromArray() by passing
      • makeBSTfromArray(min, middle-1)
      • makeBSTfromArray(middle+1, max)

    Important Condition in makeBSTfromArray():

    • Return NULL if min index is greater than max index.

    Let me know if we have more refined solution for this assignment.

    Source Code:

    TNode * make BSTfromArray(int a[], int min, int max){

        if(min>max) return NULL;
        
        int midIdx = (min + max )/2;
        cout << endl << " a[" << midIdx <<"]: "<<a[midIdx];
        
        TNode *nodePtr = createNode(a[midIdx]);
        nodePtr->left = makeBSTfromArray(a, min, midIdx-1);
        nodePtr->right = makeBSTfromArray(a, midIdx+1, max);
        
        return nodePtr;
    }
    

    Input Array = {3,4,5,6,7,8,9,10,12,13}

    Output of makeBSTfromArray:
    a[4]: 7
    a[1]: 4
    a[0]: 3
    a[2]: 5
    a[3]: 6
    a[7]: 10
    a[5]: 8
    a[6]: 9
    a[8]: 12
    a[9]: 13

    In Order Travers Result:
    [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 12 ] [ 13 ]


  • 0
    N

    Can anyone let me know if this works. if not please list the errors.

    Blessings,

    Nick

    struct TNode*
        {
            int val;
            TNode* left;
            TNode* right;
            TNode(int val)
            {
                this->val = val;
                left = right = nullptr;
            }
        }
        TNode* arrayToBst(vector<int>& nums)
        {
            if(nums.size() == 0)
                return nullptr
            return arrayToBstUtil(nums, left, right);
        }
        TNode* arrayToBstUtil(vector<int>& nums, int left, int right);
        {
            int mid = (left+right)/2;
            if(left > right)
                return nullptr;
            TNode* node = new TNode(nums[mid]);
            node->left = arrayToBstUtil(nums,left,mid-1);
            node->right = arrayToBstUtil(nums,mid+1, right);
            return node;
        }
    

  • 0
    R

    @nr1286 said in Given a sorted array, write an algorithm to create a binary search tree with minimal height.:

    return arrayToBstUtil(nums, left, right);

    I think it should be:

    return arrayToBstUtil(nums,0,nums.size());


Log in to reply