Minimal Tree

Easy
0/40
Average time to solve is 15m
profile
Contributed by
12 upvotes
Asked in companies
AmazonAppleFacebook

Problem statement

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 -:

alt text

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.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases, then ‘T’ test cases follow.

The first line of each test case consists of a single integer ‘N’, representing the number of elements in array ‘Arr’.

The second line of each test case consists of ‘N’ space-separated integers, representing array ‘Arr’.

Output format :

For each test case, in a separate line ‘Correct’ will be printed if you convert the given array in the height-balanced tree correctly, otherwise ‘Incorrect’ will be printed.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1  <= N <= 10^4
-10^9 <= Arr[i] <= 10^9


Time limit: 1 sec

Sample Input 1 :

2
1
1
5
-10 -5 2 4 5

Sample Output 1 :

Correct
Correct

Explanation of Sample Input 1 :

Test case 1:
There is only one node, so the correct way to convert it to the height-balanced binary search tree is to create a tree having a single node with the data ‘1’

Test case 2:
See the problem statement for an explanation.

Sample Input 2 :

2
5
1 2 3 4 5
2
-10 25

Sample Output 2 :

Correct
Correct
Hint

The middle element of the array is the root of this binary search tree.

Approaches (1)
Recursion

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.
  • The required height-balanced binary search tree will be returned by minimalTreeHelper(0, N-1).
Time Complexity

O(N),  where ‘N’ is the number of elements in array ‘Arr’. 

 

Here, in each recursive step, we divide the array into two halves and recur on both of them. Also, each recursive step takes O(1) time, thus its recurrence relation will be T(N) = 2*T(N/2) + f(1)  By Master Theorem, its time complexity will be O(N).

Space Complexity

O(log(N)),  where ‘N’ is the number of elements in array ‘Arr’. 

 

The tree will be balanced, so the recursion depth will be of the order of log(N). Thus space used by the recursion stack is also of the order of log(N), and hence the space complexity will be O(log(N)).

Code Solution
(100% EXP penalty)
Minimal Tree
Full screen
Console