Convert sorted array to balanced BST

Difficulty: Easy, Asked-In: Google, Amazon, Cisco, VMWare

Key takeaway: An excellent problem to learn problem-solving using recursive (divide and conquer) and iterative (using stack and queue) approaches.

Let’s understand the problem

Write a program to convert a sorted array of integers into a Balanced Binary Search Tree.

• Each node in the tree must follow the BST property: Values of all nodes in the left subtree are less than the value of given node, values of all nodes in the right subtree are greater than the value of given node, and both left and right subtrees are also BSTs.
• In a balanced binary tree, difference in the height of left and right subtrees does not exceed 1. In other words, height of the left and right subtrees are as close to equal as possible.

Example

Discussed solution approaches

• Recursive solution using divide and conquer
• Iterative solution using BFS traversal
• Iterative solution using stack

Recursive solution using divide and conquer

Solution idea

Our goal is to maintain two crucial properties of a binary search tree at every node: 1) BST property 2) The height balance property. To achieve this, we can use the property of a sorted array to construct the BST. How can we do this? Let's think!

If we select any value X[i] in the sorted array, then it is greater than all values from X[0] to X[i - 1] and less than all values from X[i + 1] to X[n - 1]. So, if we make X[i] the root of BST, we can allocate i number of nodes (X[0] to X[i - 1]) to the left subtree and n - i - 1 number of nodes (X[i + 1] to X[n - 1]) to the right subtree.

To ensure that the tree is balanced, the best approach would be to allocate equal number of nodes to both left and right subtrees. In other words, choosing the value at mid-index as the root would be the best choice.

So the overall idea is based on divide and conquer approach: We divide the array into two equal parts and keep the middle element as root. After this, we recursively build BST for left and right subarray by calling the same function.

Solution steps

Here are divide and conquer steps to construct a balanced BST from a sorted array. Suppose we define a function sortedArrayToBST(X[], l, r) to return the root of constructed BST. Here l is left end of array and r is the right end.

Divide: Using the mid-point, we divide the array into two equal parts and create a new BST node with the value X[mid].

int mid = l + (r - l)/2
BSTNode root = new BSTNode(X[mid])

Conquer: Both the left and right halves are smaller versions of the same problem i.e. constructing a balanced BST from a sorted array of size n/2. Left half = X[l] to X[mid - 1], Right half = X[mid + 1] to X[r].

• We recursively call the same function on the left half to build balanced left subtree.
• We recursively call the same function on the right half to build balanced right subtree.

root->left = sortedArrayToBST(X, l, mid - 1)
root->right = sortedArrayToBST(X, mid + 1, r)

Combine: After the completion of both recursive calls, we will have a balanced BST. We will return the pointer to the root element.

Base case: This is the smallest version of the problem where recursion will terminate and directly return the solution. If we observe, the case of empty array i.e. l > r is the situation of base case.

Solution code C++

struct BSTNode
{
    int data;
    BSTNode* left;
    BSTNode* right;

    BSTNode(int val)
    {
        data = val;
        left = right = NULL;
    }
};

BSTNode* sortedArrayToBST(int X[], int l, int r)  
{  
    if (l > r)  
        return NULL;
    int mid = l + (r - l)/2;
    BSTNode* root = new BSTNode(X[mid]);
    root->left = sortedArrayToBST(X, l, mid - 1);
    root->right = sortedArrayToBST(X, mid + 1, r);
    return root; 
}

Time and space complexity analysis

We are dividing the problem into two smaller sub-problems of equal size and recursively constructing the BST. Here time complexity of the divide and combine steps are O(1). So recurrence relation for time complexity is T(n) = 2T(n/2) + O(1). We can analyse it using the master theorem or recursion tree method.

Based on master theorem, if T(n) = aT(n/b) + O(n^k)

• Case 1: When k < logb(a) then T(n) = O(n^logb(a))
• Case 2: When k = logb(a) then T(n) = O(n^k * logn)
• Case 3: When k > logb(a) then T(n) = O(n^k)

Let's compare the above recurrence relation with master theorem recurrence:

• T(n) = aT(n/b) + O(n^k)
• T(n) = 2T(n/2) + O(n^0)

Here a = 2, b = 2 and k = 0. So logb(a) = log2(2) = 1, which is greater than k. So we can apply case 1 of the master theorem. Time complexity T(n) = O(n^logb(a)) = O(n^1) = O(n).

At each step of recursion, input size is decreasing by 1/2 and depth of the recursion tree will be O(logn). So space used by recursion call stack will be O(logn). Space complexity = O(logn).

Iterative solution using BFS Traversal

Solution idea

Another idea would be to construct a balanced binary search tree (BST) using level order traversal or breadth-first search. How do we do this? Let's think!

If we observe the balanced BST, then root node will be the middle element of array, which cover the entire range [l, r].

• Left child of root will be the middle value of subarray [l, mid - 1] and cover the range [l, mid - 1].
• Right child of root will be the middle value of subarray [mid + 1, r] and cover the range [mid + 1, r].

In this way, every node will cover some range of values and value of that node will be the middle element of that range. Now the critical question is: How do we build a balanced BST using this idea and level order traversal? Here are the steps.

Solution steps

One idea is clear: We need to track the range (left and right index) of each node so that we can find its left and right child during traversal. For this, we define a MyNode class which stores three things: BST node pointer, left range and right range of a given node. We will use queue to store MyNode.

class MyNode 
{
    BSTNode node
    int l
    int r

    MyNode(BSTNode n, int lValue, int rValue) 
    {
        node = n
        l = lValue
        r = rValue
    }
}

Step 1: The middle element of array is the root of our BST. So we create a BST node of this value and add it to the queue with the left and right indices of the range.

Step 2: Now we run a loop till queue is empty. Inside the loop, we first remove the root node from the queue and update left and right child of it: 1) Middle of left subarray [l, mid - 1] as the left child 2) Middle of right subarray [mid + 1, r] as the right child.

• We first create a BST node with the middle value of left subarray [l, mid - 1], update it as the left child of root and add it to the queue with updated left and right indices of its range.
• After this, we create a BST node with the middle value of right subarray [l, mid - 1], update it as the right child of root and add it to the queue with updated left and right indices of its range.

Step 3: Similarly, we keep removing nodes from the queue in the loop and updating left and right children based on the middle value of the node range. By end of the process, we return a pointer to the root node of the constructed tree.

Solution code C++

struct MyNode 
{
    BSTNode *node;
    int l;
    int r;

    MyNode(BSTNode *n, int lValue, int rValue) 
    {
        node = n;
        l = lValue;
        r = rValue;
    }
};

BSTNode* sortedArrayToBST(int X[], int n) 
{
    if (n == 0)
        return NULL;

    queue<MyNode> Q;
    int l = 0, r = n - 1;
    int value = X[l + (r - l) / 2];

    BSTNode *root = new BSTNode(value);
    Q.emplace(root, l, r);

    while (Q.empty() == false) 
    {
        MyNode curr = Q.front();
        Q.pop();
        int mid = curr.l + (curr.r - curr.l) / 2;

        if (mid != curr.l) 
        {
            BSTNode *leftChild = new BSTNode(X[curr.l + (mid - 1 - curr.l) / 2]);
            curr.node->left = leftChild;
            Q.emplace(leftChild, curr.l, mid - 1);
        }

        if (mid != curr.r) 
        {
            BSTNode *rightChild = new BSTNode(X[mid + 1 + (curr.r - mid - 1) / 2]);
            curr.node->right = rightChild;
            Q.emplace(rightChild, mid + 1, curr.r);
        }
    }
    return root;
}

Time and space complexity analysis

At each iteration of the while loop, we are removing one node from the queue, updating left and right child and adding both to the queue. In other words, we are performing constant number of operations at each iteration. So time complexity = n* O(1) = O(n).

Overall space complexity = Size of the queue + Extra space for each node to store left and right indices of the range = O(n) + O(n) = O(n).

Iterative solution using stack

Solution idea and steps

Similar to above approach, we can construct balanced BST using stack to keep track of nodes and indices. How can we do this? Let's understand!

Here we use stack S to stores BST nodes and two extra stack (leftIndexStack and rightIndexStack) to store left and right indices of the range.

Step 1: We first create root node and push it onto a stack S. We also push left and right indices (0 and n - 1) of range onto their respective stacks.

Step 2: Now we run a loop until the stack S is empty. At each iteration of the loop: We pop top node and indices from their respective stacks and choose middle element of the current subarray (defined by indices) as the value for the BST node.

• If left subarray is non-empty, we create a new left child for the current node. After this: We push left child, the left and right indices of the left subarray onto their respective stacks.
• If the right subarray is non-empty, we create a new right child for the current node. After this: We push right child, the left and right indices of the left subarray onto their respective stacks.

Step 3: By the end of loop, we return the root node of the constructed binary search tree.

Solution code C++

struct BSTNode 
{
    int value;
    BSTNode* left;
    BSTNode* right;

    BSTNode(int x)
    {
        value = x;
        left = NULL; 
        right = NULL;
    }    
};

BSTNode* sortedArrayToBST(int X[], int n) 
{
    if (n == 0) 
        return nullptr;

    stack<BSTNode *> S;
    BSTNode* root = new BSTNode(0);
    S.push(root);

    stack<int> leftIndexStack;
    leftIndexStack.push(0);

    stack<int> rightIndexStack;
    rightIndexStack.push(n - 1);

    while (S.empty() == false) 
    {
        BSTNode* curr = S.top();
        S.pop();
        
        int l = leftIndexStack.top();
        leftIndexStack.pop();
        
        int r = rightIndexStack.top();
        rightIndexStack.pop();
        
        int mid = l + (r - l) / 2;
        curr->value = X[mid];
        if (l <= mid - 1) 
        {
            curr->left = new BSTNode(0);
            S.push(curr->left);
            leftIndexStack.push(l);
            rightIndexStack.push(mid - 1);
        }
        
        if (mid + 1 <= r) 
        {
            curr->right = new BSTNode(0);
            S.push(curr->right);
            leftIndexStack.push(mid + 1);
            rightIndexStack.push(r);
        }
    }
    
    return root;
}

Time and space complexity analysis

We are adding and removing each node only once from the stack. Similarly, we are removing and adding left and right range for each node only once from their respective stacks. In simple words, we are performing constant number of operations at each iteration. So time complexity = n* O(1) = O(n).

Overall space complexity = Size of the stack to store BST nodes + Size of stack for storing left and right indices of the range = O(logn) + O(logn) = O(logn).

Critical ideas to think!

• Does the above solution work for both odd and even cases of input size?
• Can we solve this problem using in-order traversal?
• Can we solve this problem using constant extra space?
• How can we analyze the time complexity of the recursive solution using the recursion tree method?
• Why is the size of the queue O(n) in the BSF approach?
• Why is the size of the stack in the 3rd approach O(logn)?
• In the recursive solution, can we add a base condition for a one-size input to reduce the number of recursive calls?
• How can we modify the above code if the array is sorted in decreasing order?

Suggested coding problems to practice

• Convert sorted singly linked list to balanced BST.
• Convert sorted doubly linked list to balanced BST.
• Convert unbalanced BST to a balanced BST.
• Convert binary tree to a balanced binary search tree.
• Cover binary search tree to doubly linked list.
• Check that given binary tree is BST or not.

Please feel free to message below if you find any errors or want to share additional insights. Enjoy learning, enjoy algorithms!