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


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

  • 1
    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());


  • 0
    G
    -(Node*)sortedArrayToBST:(NSArray*)initial startAt:(int)start endAt:(int)end {
        if(start > end) return nil;
        int mid = (int)start + floor((end - start)/2);
        Node* node = [[Node alloc] initWithData:[[initial objectAtIndex:mid] intValue]];
        node.left = [self sortedArrayToBST:initial startAt:start endAt:mid-1];
        node.right = [self sortedArrayToBST:initial startAt:mid+1 endAt:end];
        return node;
    }
    
    -(void)inOrderTraversal:(Node*)node{
        if(node != nil){
            [self inOrderTraversal:node.left ];
            NSLog(@"%i", node.data);
            [self inOrderTraversal:node.right ];
        }
    }
    
    -(void)preOrderTraversal:(Node*)node{
        if(node != nil){
            NSLog(@"%i", node.data);
            [self inOrderTraversal:node.left ];
            [self inOrderTraversal:node.right ];   
        }
    }
    
    -(void)postOrderTraversal:(Node*)node{
        if(node != nil){
            [self inOrderTraversal:node.left ];
            [self inOrderTraversal:node.right ];
            NSLog(@"%i", node.data);   
        }
    }
    
    

  • 0
    S

    /**
    * Create Bst Using Sorted Array if we just add this to tree we get skewed
    * tree so we select mid of array and add elements to left to left subtree
    * and elements to right subtree and call this function recursively
    *
    * @param min
    * @param max
    * @param array
    * @return
    */
    public Node<Integer> CreateBstUsingSortedArray(int min, int max, int[] array) {
    if (min == max) {
    return new Node<Integer>(array[min]);
    }
    if (min > max) {
    return null;
    }
    int mid = (min + max) / 2 + (min + max) % 2;
    System.out.println("Mid: " + mid);
    Node<Integer> node = new Node<Integer>(array[mid]);
    node.leftChild = CreateBstUsingSortedArray(min, mid - 1, array);
    node.rightChild = CreateBstUsingSortedArray(mid + 1, max, array);
    return node;

    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.