New update is available. Click here to update.

Minimal Tree

Posted: 26 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.