# Minimal Tree

Posted: 26 Feb, 2021

Difficulty: Easy

#### You are given an array ‘Arr’ consisting of ‘N’ distinct integers. Elements in array ‘Arr’ are sorted in increasing order. Your task is to convert it to a height-balanced binary search tree.

#### A binary tree is height-balanced when the height of the two subtrees of every node never differs by more than one.

#### Note :

```
1. There can be more than one way to convert an array to a height-balanced binary tree. You can find any one of them.
```

#### Example :

```
Consider an array ‘Arr’ = [-10, -5, 2, 4, 5], one way to convert it to a height-balanced binary tree is -:
```

```
Here, You can see that the height of the left and right subtree of the node having the data ‘2’ is 2 and 2 respectively, i.e both are the same, and the height of the left and the right tree of the node having the data ‘-10’, is 0, 1 respectively, i.e differ by only 1, and the height of left and right subtree of the node having the data ‘4’, is also 0 and ‘1’ respectively, i.e differ by only ‘1’. Thus this binary search tree is height-balanced. Also, note that this is not the only way to convert this array to a height-balanced binary search tree.
```

Approach 1

The root of the height-balanced binary search tree will be the middle element of the given array, and its left subtree will be the height-balanced binary search formed by the elements at the left of the middle, and its right subtree will be the height-balanced binary search formed by the elements at the right of the middle elements. So, we can form tree recursively as follows:

**Algorithm**

- Initialize two integer variables
**‘left’ := 0**and**‘right’ := N-1.** **Create a recursive function minimalTreeHelper(left, right) and in each recursive call do the following:**- If
**left > right**, then return**NULL**. - Initialize an integer variable
**mid:= (left + right)/2**. - Create a node of a binary tree having the data
**Arr[mid]**and make it the**root**of this tree. - The left subtree of the root will be returned by
**minimalTreeHelper(left, mid-1)**and the right subtree of the node will be returned by**minimalTreeHelper(mid+1, right).** - Return
**root.**

- If
**The required height-balanced binary search tree will be returned by minimalTreeHelper(0, N-1).**

SIMILAR PROBLEMS

# Two Sum II - Input Array Is Sorted

Posted: 4 Mar, 2022

Difficulty: Moderate

# Ninja And Matrix

Posted: 12 Apr, 2022

Difficulty: Easy

# Ninja In Interview

Posted: 13 Apr, 2022

Difficulty: Easy

# Missing Number

Posted: 17 Apr, 2022

Difficulty: Easy

# Min Heap

Posted: 5 May, 2022

Difficulty: Moderate