Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# 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.
*/

/*
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 --------
``````

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# 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.
*/

/*
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 --------
``````

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Hosted By
Ryan Valles
Founder, Interview Kickstart
Accelerate your Interview prep with Tier-1 tech instructors
360° courses that have helped 14,000+ tech professionals
100% money-back guarantee*