Last Updated: 26 Feb, 2021
Minimal Tree
Easy
Asked in companies
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.
Approaches
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).
Similar problems