Last Updated: 20 Mar, 2021
Convert Sorted Array to BST
Easy
Asked in companies
You have been given a sorted array of length ‘N’. You need to construct a balanced binary search tree from the array. If there can be more than one possible tree, then you can return any.
Note:
1. A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.
2. A binary search tree is a binary tree data structure, with the following properties
a. The left subtree of any node contains nodes with value less than the node’s value.
b. The right subtree of any node contains nodes with values equal to or greater than the node’s value.
c. Right, and left subtrees are also binary search trees.
Example:
Below tree, is a balanced binary search tree
Below tree is not a balanced tree as the height of the left subtree and right subtree of node ‘5’ differs by more than 1. Moreover, the tree is also not a BST as node ‘2’ is less than node ‘3’ but ‘2’ is the right child of ‘3’.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains an integer ‘N’ which denotes the number of elements in the array.
The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array in strictly increasing order.
Output Format:
For each test case, the output will be “1” if you have returned the correct answer, else it will be “0”.
Note :
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 3000
1 <= arr[i] <= 10 ^ 5
Where 'arr[i]’ is the value of i-th element of the given array
arr[0] < arr[1] < arr[2] . . . < arr[N].
Time Limit: 1 sec
Approaches
As the given array is sorted and we want a balanced tree such that every node has a right subtree with a greater value and a left subtree with a smaller value. We can think of making the middle element of the array root node, this will ensure that both left and right subtree have equal elements thus maintaining the balance of the tree. All elements left of middle elements are smaller and go into the left subtree of the root node. Elements on the right of middle elements are greater thus goes on the right subtree. And also for making the left subtree a ‘balanced BST’ we can further divide it into two halves, same for the right subtree. Recursively following the procedure overall nodes will result in a balanced binary search tree.
Algorithm :
- Let’s say we need to find a balanced BST for ‘ARR[1:N]’, where ‘N’ is the size of array ‘ARR’.
- Base case - if ‘N == 1’ i.e. only one element is present, then make it a root node.
- Else, Declare a variable say ‘mid’ that stores the middle index of the array.
- The ‘ARR[mid]’ forms the root node of balanced BST
- For left subtree recursively call the function with the left part of array i.e ‘ARR[1: mid-1]’
- For the right subtree recursively call the function with the right part of the array i.e. ‘ARR[mid+1:N]’
- Add returned left subtree and right subtree to the left and right child, respectively of the root node.
- Return root node.
We can solve the problem iteratively by using a stack data structure to keep track of the child nodes and ranges in an array that needs to be added to the tree.
Algorithm :
- Declare a tuple/struct data structure say ‘NODE_DATA’, that stores [ ‘node’, ‘low’, ‘high’ ]. Where ‘node’ is a pointer to any particular node in a tree, ‘low’ and ‘high’ are the low range and high range in array respectively for that particular node.
- Declare a stack of ‘NODE_DATA’.
- Create a root node.
- Declare a ‘NODE_DATA’ variable say ‘ROOT_DATA’ for root node of tree with [ ‘node’ = root node, ‘low’ = ‘1’, ‘high’ = ‘N’ ]
- Push ‘NODE_DATA’ into the stack.
- Run a loop until the stack is not empty.
- Pop the top element from the stack and store it in a variable say ‘CURR_NODE’.
- If ‘CURR_NODE -> low’ == ‘CURR_NODE -> high’
- ‘CURR_NODE -> node -> value’ = ‘arr[ low ]’
- Else
- Find ‘mid’ index for the range [ ‘CURR_NODE - > low’ : ‘CURR_NODE -> high’ ]
- Set ‘CURR_NODE -> node -> value’ = ‘arr[ mid ]’.
- Create two nodes say ‘leftChild’ and ‘rightChild’ for the left subtree and right subtree of ‘CURR_NODE’ and set ‘CURR_NODE -> node -> left’ = ‘leftChild’ and ‘CURR_NODE -> node -> right’ = ‘rightChild’.
- Now we have to push this newly created node into the stack for further exploration in the tree.
- Create two ‘NODE_DATA’ variables [ ‘node’ = ‘leftChild’ , ‘low’ = ‘CURR_NODE -> low’, ‘high’ = ‘mid’ - 1 ] and [ ‘node’ = ‘rightChild’, ‘low’ = ‘mid’ + 1, ‘high’ = ‘CURR_NODE -> high’ ].
- Push both variables into the stack.
- Return the ‘root node’.