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

• 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 ]

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

• return arrayToBstUtil(nums, left, right);

I think it should be:

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

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

``````

• /**
* 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;

``}``

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