Convert Sorted Array To Binary Search Tree

Companies:
  • Amazon Interview Questions
  • Apple Interview Questions
  • Cisco Interview Questions
  • Facebook Interview Questions
  • Microsoft Interview Questions

Problem Statement

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Sample Test Case

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Problem Solution

Since the given array is sorted, we can assume it to be the result of an in-order traversal of the given tree.

In which case the mid value of the given sorted array would represent the root of one possible BST that can be constructed from the given array elements.

To be in alignment with the definition of a Binary Search Tree, the elements in the array to the left of the mid value, would contribute to the left subtree of our root while the elements in the array to the right of the mid value, would contribute to the right subtree of our root.

Hence we can recursively construct out binary search tree, by using binary search algorithm on the array, to construct the root, left and right subtree respectively by recursively invoking the sortedArrayToBST method with appropriate boundary conditions, that of low, mid -1 for the left subtree and mid+1, high for the right subtree.

The base condition that would terminate the recursion would then be if low boundary index exceeds high boundary index, in which case return null.

Complexity Analysis

 Time complexity: O(n), where n is the length of the array.

Space Complexity: O(h) for recursion call stack, where h is the height of the tree.

Code Implementation

// C++ program to print BST in given range
#include<bits/stdc++.h>
using namespace std;

/* A Binary Tree node */
class TreeNode
{
    public:
    int data;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* newNode(int data);

/* A function that constructs Balanced
Binary Search Tree from a sorted array */
TreeNode* sortedArrayToBST(int arr[],
                        int start, int end)
{
    /* Base Case */
    if (start > end)
    return NULL;

    /* Get the middle element and make it root */
    int mid = (start + end)/2;
    TreeNode *root = newNode(arr[mid]);

    /* Recursively construct the left subtree
    and make it left child of root */
    root->left = sortedArrayToBST(arr, start,
                                    mid - 1);

    /* Recursively construct the right subtree
    and make it right child of root */
    root->right = sortedArrayToBST(arr, mid + 1, end);

    return root;
}

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
TreeNode* newNode(int data)
{
    TreeNode* node = new TreeNode();
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

/* A utility function to print
preorder traversal of BST */
void preOrder(TreeNode* node)
{
    if (node == NULL)
        return;
    cout << node->data << " ";
    preOrder(node->left);
    preOrder(node->right);
}

// Driver Code
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    /* Convert List to BST */
    TreeNode *root = sortedArrayToBST(arr, 0, n-1);
    cout << "PreOrder Traversal of constructed BST \n";
    preOrder(root);

    return 0;
}

 

public class Main 
{
    int val;
    Main left;
    Main right;
    Main(){}
    
    Main(int val) 
    { 
        this.val = val; 
    }
    
    static void printPreorder(Main node) 
    { 
        if (node == null) 
            return; 
        System.out.print(node.val + " "); 

        printPreorder(node.left); 
        printPreorder(node.right); 
    } 

    static public Main BST_convert(int[] num) 
    {
        if (num.length == 0) 
        {
            return null;
        }
        
        Main head = helper(num, 0, num.length - 1);
        return head;
    }

    static public Main helper(int[] num, int low, int high) 
    {
        if (low > high) 
            return null;
    
        int mid = (low + high)/2;
        
        Main node = new Main(num[mid]);
        node.left = helper(num, low, mid - 1);
        node.right = helper(num, mid + 1, high);
        return node;
    }
    
    public static void main(String[] args) 
    {
        Main t = new Main();

        
        int arr[] = new int[7]; 
        arr[0]=1;
        arr[1]=2;
        arr[2]=3;
        arr[3]=4;
        arr[4]=5;
        arr[5]=6;
        arr[6]=7;
        
        t = BST_convert(arr);
        
        printPreorder(t);
        
    }
    
}

 

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(root): 
    if root: 
        print(root.val, end = " "), 
        preorder(root.left) 
        preorder(root.right) 


def BST_convert(nums):
    return helper(nums, 0, len(nums)-1)

def helper(nums, l, r):
    if l <= r:
        mid = l + (r-l)//2
        root = TreeNode(nums[mid])
        root.left = helper(nums, l, mid-1)
        root.right = helper(nums, mid+1, r)
        return root

arr= [1,2,3,4,5,6,7]
t = TreeNode()

t = BST_convert(arr);
preorder(t)

 

Scroll to Top