Arrays: Convert a sorted array into a binary search tree using recursive approach
In this article, we will convert the given sorted array into a binary search tree and print in preorder traversal of that tree
Approach
- Since the approach is recursive, the idea is to find the middle element of the given sorted array and make it as a root
- Then find the middle element for the left side of array and make it as the left child of the root element
- Similarly find the middle element of the right side of array and make it as the right child of the root element
- Do this recursively
- Finally print the binary tree in preorder traversal
Complexity
Time Complexity : O(n) , since we are visiting each element of array exactly once
Space Complexity: O(1)
Java Code
class ConvertSortedArrayToBSTRecursive{
class Node {
int data;
Node left, right;
Node(int d) {
data = d;
left = right = null;
}
}
static Node root;
Node arraytoBst(int array[], int start, int end) {
if (start > end) {
return null;
}
int mid = (start + end) / 2;
Node node = new Node(array[mid]);
node.left = arraytoBst(array, start, mid - 1);
node.right = arraytoBst(array, mid + 1, end);
return node;
}
void preOrder(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
public static void main(String[] args) {
ConvertSortedArrayToBSTRecursive a = new ConvertSortedArrayToBSTRecursive();
int sortedArray[] = new int[]{1, 2, 3, 4, 5, 6, 7};
System.out.println("Sorted array: ");
for(int element: sortedArray){
System.out.print(element + " ");
}
int n = sortedArray.length;
root = a.arraytoBst(sortedArray, 0, n - 1);
System.out.println();
System.out.println("Preorder traversal of constructed BST: ");
a.preOrder(root);
}
}
Output
Sorted array:
1 2 3 4 5 6 7
Preorder traversal of constructed BST:
4 2 1 3 6 5 7
Thanks for feedback.