Balanced BST From A Sorted Array Problem

Given N distinct integers in a sorted array, build a balanced binary search tree (BST).

A BST is called balanced if the number of nodes in the left and right subtrees of every node differs by at most one.

Example

Input: [8 10 12 15 16 20 25]

Output:

Notes

Input Parameters: There is only one argument denoting array a.

Output: You have to return the root root of the balanced BST that you created. There can be multiple balanced BST for given input. So, you are free to return any of the valid one.

Only thing you have to consider is that it is a valid balanced BST of a.

Constraints:

• a is sorted.
• a contains distinct integers.
• -2 * 10^9 <= a[i] <= 2 * 20^9
• 1 <= N <= 10^5

Solutions

Balanced tree has two definitions:

1) weight-balanced: here we focus on the difference in number of nodes in the left and right subtrees. (Perfect tree)

2) height-balanced: here we focus on the difference in height of the left and right subtrees. (AVL tree, Red-Black tree)

In this problem we need to consider weight-balanced tree. Only thing we need to know in order to solve the problem is what should be the root of the tree. We need to choose the middle element as the root and this is enough to solve the problem.

Why middle element? Suppose in our balanced BST left subtree of the root contains l nodes and right subtree of the root contains r nodes.

Then we can write it as: number of nodes in left subtree + 1 (root) + number of nodes in right subtree = total number of nodes in tree.

l + 1 + r = N.

with |l – r| <= 1.

so we can write it as:

l + r = N – 1,

and |l – r| <= 1 has 3 possibilities,

1) l = r

or

2) l = r + 1

or

3) l = r – 1

Now let’s think what should be l and r when:

1) when N is odd:

try first option l = r,

r + r = N – 1

2 * r = N – 1

r = (N – 1) / 2 is possible because N is odd hence N – 1 is even!

try second option l = r + 1,

r + 1 + r = N – 1

r + r = N – 2

2 * r = N – 2

r = (N – 2) / 2 is not possible because N is odd hence N – 2 is also odd hence r will not be an integer!

try third option l = r – 1,

r – 1 + r = N – 1

2 * r = N

r = N / 2 is not possible because N is odd hence r will not be an integer!

2) when N is even:

try first option l = r,

r + r = N – 1

2 * r = N – 1

r = (N – 1) / 2 is not possible because N is even hence N – 1 is odd hence r will not be an integer!

try second option l = r + 1,

r + 1 + r = N – 1

r + r = N – 2

2 * r = N – 2

r = (N – 2) / 2 is possible because N is even hence N – 2 is also even!

try third option l = r – 1,

r – 1 + r = N – 1

2 * r = N

r = N / 2 is possible because N is even hence N – 2 is also even!

When N is odd we need to select (N – 1) / 2 th element (the middle element, 0-indexed) as the root of the tree. Both left and right subtrees will receive the same number of nodes.

When N is even then we need to select

1) (N – 1) / 2 th element (left middle element, 0-indexed) as the root of the tree. In this case right subtree will receive one more node than left subtree.

or

2) N / 2 th element (right middle element, 0-indexed) as the root of the tree. In this case, left subtree will receive one more node than right subtree.

Problem we are solving is, given N elements build a balanced BST. Now once we have fixed our root we need to solve the same problem again with smaller constraints hence we can use the same function by recursive calls!

Time Complexity:

T(N) = 2 * T(N / 2) + O(1) which will be O(N).

More intuitive explanation is: function is just creating a new node and assigning a value to that node, that is O(1) computation. And in our tree we will create exactly N nodes!

Auxiliary Space:

O(log N).

That’s maximum recursion depth.

Space Complexity:

O(N).

// -------- START --------

/*
 * Complete the function below.
 */

/*
    For your reference. 
    struct TreeNode
    {
        int val;
        TreeNode* left_ptr;
        TreeNode* right_ptr;
        TreeNode(int _val = 0)
        {
            val = _val;
            left_ptr = NULL;
            right_ptr = NULL;
        }
    };
*/

// build tree using values (a[l], a[l+1], ..., a[r]).
TreeNode * build_balanced_bst_helper(int l, int r, vector &a)					
{
	if (l > r)	
	{
		return NULL;
	}
	int m = l + (r - l) / 2;
	// to build balanced tree we need to choose the middle element as the root 
	TreeNode *temp = new TreeNode(a[m]);											
	// recursively create subtree and add it as left child
	temp->left_ptr = build_balanced_bst_helper(l, m - 1, a);						
	// recursively create subtree and add it as right child 
	temp->right_ptr = build_balanced_bst_helper(m + 1, r, a);						
	return temp;
}

TreeNode * build_balanced_bst(vector a)
{
	int N = a.size();
	// build balanced BST
	return build_balanced_bst_helper(0, N - 1, a);									
}

// -------- END --------