Given a sorted array. Write a function that creates a Balanced Binary Search Tree using array elements.
Examples:
Input: arr[] = {1, 2, 3}
Output: A Balanced BST
2
/ \
1 3
Explanation: all elements less than 2 are on the left side of 2 , and all the elements greater than 2 are on the right sideInput: arr[] = {1, 2, 3, 4}
Output: A Balanced BST
3
/ \
2 4
/
1
Sorted Array to Balanced BST By Finding The middle element
The idea is to find the middle element of the array and make it the root of the tree, then perform the same operation on the left subarray for the root’s left child and the same operation on the right subarray for the root’s right child.
Follow the steps mentioned below to implement the approach:
- Set The middle element of the array as root.
- Recursively do the same for the left half and right half.
- Get the middle of the left half and make it the left child of the root created in step 1.
- Get the middle of the right half and make it the right child of the root created in step 1.
- Print the preorder of the tree.
Below is the implementation of the above approach:
C++
// C++ program to print BST in given range#include <bits/stdc++.h>using namespace std;/* A Binary Tree node */class TNode {public: int data; TNode* left; TNode* right;};TNode* newNode(int data);/* A function that constructs BalancedBinary Search Tree from a sorted array */TNode* 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; TNode* 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 nodewith the given data and NULL left and rightpointers. */TNode* newNode(int data){ TNode* node = new TNode(); node->data = data; node->left = NULL; node->right = NULL; return node;}/* A utility function to printpreorder traversal of BST */void preOrder(TNode* node){ if (node == NULL) return; cout << node->data << " "; preOrder(node->left); preOrder(node->right);}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); /* Convert List to BST */ TNode* root = sortedArrayToBST(arr, 0, n - 1); cout << "PreOrder Traversal of constructed BST \n"; preOrder(root); return 0;}// This code is contributed by rathbhupendra |
Java
// Java program to print BST in given range// A binary tree nodeclass Node { int data; Node left, right; Node(int d) { data = d; left = right = null; }}class BinaryTree { static Node root; /* A function that constructs Balanced Binary Search Tree from a sorted array */ Node 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; Node node = new Node(arr[mid]); /* Recursively construct the left subtree and make it left child of root */ node.left = sortedArrayToBST(arr, start, mid - 1); /* Recursively construct the right subtree and make it right child of root */ node.right = sortedArrayToBST(arr, mid + 1, end); return node; } /* A utility function to print preorder traversal of BST */ 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) { BinaryTree tree = new BinaryTree(); int arr[] = new int[] { 1, 2, 3, 4, 5, 6, 7 }; int n = arr.length; root = tree.sortedArrayToBST(arr, 0, n - 1); System.out.println( "Preorder traversal of constructed BST"); tree.preOrder(root); }}// This code has been contributed by Mayank Jaiswal |
Python
# Python code to convert a sorted array# to a balanced Binary Search Tree# binary tree nodeclass Node: def __init__(self, d): self.data = d self.left = None self.right = None# function to convert sorted array to a# balanced BST# input : sorted array of integers# output: root node of balanced BSTdef sortedArrayToBST(arr): if not arr: return None # find middle index mid = (len(arr)) // 2 # make the middle element the root root = Node(arr[mid]) # left subtree of root has all # values <arr[mid] root.left = sortedArrayToBST(arr[:mid]) # right subtree of root has all # values >arr[mid] root.right = sortedArrayToBST(arr[mid+1:]) return root# A utility function to print the preorder# traversal of the BSTdef preOrder(node): if not node: return print node.data, preOrder(node.left) preOrder(node.right)# driver program to test above function"""Constructed balanced BST is 4/ \2 6/ \ / \1 3 5 7"""arr = [1, 2, 3, 4, 5, 6, 7]root = sortedArrayToBST(arr)print "PreOrder Traversal of constructed BST ",preOrder(root)# This code is contributed by Ishita Tripathi |
C
#include <stdio.h>#include <stdlib.h>/* A Binary Tree node */struct TNode { int data; struct TNode* left; struct TNode* right;};struct TNode* newNode(int data);/* A function that constructs Balanced Binary Search Tree * from a sorted array */struct TNode* 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; struct TNode* 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. */struct TNode* newNode(int data){ struct TNode* node = (struct TNode*)malloc(sizeof(struct TNode)); node->data = data; node->left = NULL; node->right = NULL; return node;}/* A utility function to print preorder traversal of BST */void preOrder(struct TNode* node){ if (node == NULL) return; printf("%d ", node->data); preOrder(node->left); preOrder(node->right);}/* Driver program to test above functions */int main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); /* Convert List to BST */ struct TNode* root = sortedArrayToBST(arr, 0, n - 1); printf("n PreOrder Traversal of constructed BST "); preOrder(root); return 0;} |
C#
using System;// C# program to print BST in given range// A binary tree nodepublic class Node { public int data; public Node left, right; public Node(int d) { data = d; left = right = null; }}public class BinaryTree { public static Node root; /* A function that constructs Balanced Binary Search Tree from a sorted array */ public virtual Node 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; Node node = new Node(arr[mid]); /* Recursively construct the left subtree and make it left child of root */ node.left = sortedArrayToBST(arr, start, mid - 1); /* Recursively construct the right subtree and make it right child of root */ node.right = sortedArrayToBST(arr, mid + 1, end); return node; } /* A utility function to print preorder traversal of BST */ public virtual void preOrder(Node node) { if (node == null) { return; } Console.Write(node.data + " "); preOrder(node.left); preOrder(node.right); } public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7 }; int n = arr.Length; root = tree.sortedArrayToBST(arr, 0, n - 1); Console.WriteLine( "Preorder traversal of constructed BST"); tree.preOrder(root); }}// This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to print BST in given range // A binary tree node class Node{ constructor(d) { this.data = d; this.left = null; this.right = null; }}var root = null;/* A function that constructs Balanced Binary Search Tree from a sorted array */function sortedArrayToBST(arr, start, end){ /* Base Case */ if (start > end) { return null; } /* Get the middle element and make it root */ var mid = parseInt((start + end) / 2); var node = new Node(arr[mid]); /* Recursively construct the left subtree and make it left child of root */ node.left = sortedArrayToBST(arr, start, mid - 1); /* Recursively construct the right subtree and make it right child of root */ node.right = sortedArrayToBST(arr, mid + 1, end); return node;}/* A utility function to print preorder traversal of BST */function preOrder(node){ if (node == null) { return; } document.write(node.data + " "); preOrder(node.left); preOrder(node.right);}var arr = [1, 2, 3, 4, 5, 6, 7];var n = arr.length;root = sortedArrayToBST(arr, 0, n - 1);document.write("Preorder traversal of constructed BST<br>");preOrder(root);</script> |
Output
PreOrder Traversal of constructed BST 4 2 1 3 6 5 7
Time Complexity: O(N)
Auxiliary Space: O(H) ~= O(log(N)), for recursive stack space where H is the height of the tree.
Approach 2: Using queue – Iterative Approach
- First initialize a queue with root node and loop until the queue is empty.
- Remove first node from the queue and find mid element of the sorted array.
- Create new node with previously find middle node and set left child to the deque node left child if present and also set the right child with deque node right child. Enqueue the new node onto the queue. Set the right child of the dequeued node to the middle element on the left side of the sorted array. If the dequeued node has a left child, enqueue it onto the queue. Return the root node.
Below is the implementation of the above approach:
C++
#include <iostream>#include <queue>#include <vector>using namespace std;// structure of the tree nodestruct Node { int val; Node* left; Node* right;};// function to convert the array to BST// and return the root of the created treeNode* sortedArrayToBST(vector<int>& nums){ // if the array is empty return NULL if (nums.empty()) { return NULL; } int n = nums.size(); int mid = n / 2; Node* root = new Node{ nums[mid], NULL, NULL }; // initializing queue queue<pair<Node*, pair<int, int> > > q; // push the root and its indices to the queue q.push({ root, { 0, mid - 1 } }); q.push({ root, { mid + 1, n - 1 } }); while (!q.empty()) { // get the front element from the queue pair<Node*, pair<int, int> > curr = q.front(); q.pop(); // get the parent node and its indices Node* parent = curr.first; int left = curr.second.first; int right = curr.second.second; // if there are elements to process and parent node // is not NULL if (left <= right && parent != NULL) { int mid = (left + right) / 2; Node* child = new Node{ nums[mid], NULL, NULL }; // set the child node as left or right child of // the parent node if (nums[mid] < parent->val) { parent->left = child; } else { parent->right = child; } // push the left and right child and their // indices to the queue q.push({ child, { left, mid - 1 } }); q.push({ child, { mid + 1, right } }); } } return root;}// function to print the preorder traversal// of the constructed BSTvoid printBST(Node* root){ if (root == NULL) return; cout << root->val << " "; printBST(root->left); printBST(root->right);}// Driver program to test the above functionint main(){ // create a sorted array vector<int> nums = { 1, 2, 3, 4, 5, 6, 7 }; // construct the BST from the array Node* root = sortedArrayToBST(nums); // print the preorder traversal of the BST printBST(root); // Output: 4 2 1 3 6 5 7 return 0;}// THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL |
Java
import java.util.LinkedList;import java.util.Queue;// structure of the tree nodeclass Node { int val; Node left; Node right; public Node(int val) { this.val = val; this.left = null; this.right = null; }}public class Main { // function to convert the array to BST // and return the root of the created tree public static Node sortedArrayToBST(int[] nums) { // if the array is empty return null if (nums.length == 0) { return null; } int n = nums.length; int mid = n / 2; Node root = new Node(nums[mid]); // initializing queue Queue<Object[]> q = new LinkedList<>(); // push the root and its indices to the queue q.add(new Object[] { root, new int[] { 0, mid - 1 } }); q.add(new Object[] { root, new int[] { mid + 1, n - 1 } }); while (!q.isEmpty()) { // get the front element from the queue Object[] curr = q.poll(); // get the parent node and its indices Node parent = (Node)curr[0]; int[] indices = (int[])curr[1]; int left = indices[0]; int right = indices[1]; // if there are elements to process and parent // node is not null if (left <= right && parent != null) { mid = (left + right) / 2; Node child = new Node(nums[mid]); // set the child node as left or right child // of the parent node if (nums[mid] < parent.val) { parent.left = child; } else { parent.right = child; } // push the left and right child and their // indices to the queue q.add(new Object[] { child, new int[] { left, mid - 1 } }); q.add(new Object[] { child, new int[] { mid + 1, right } }); } } return root; } // function to print the preorder traversal // of the constructed BST public static void printBST(Node root) { if (root == null) { return; } System.out.print(root.val + " "); printBST(root.left); printBST(root.right); } // Driver program to test the above function public static void main(String[] args) { // create a sorted array int[] nums = { 1, 2, 3, 4, 5, 6, 7 }; Node root = sortedArrayToBST(nums); printBST(root); }} |
Python3
from typing import Listfrom queue import Queue# structure of the tree nodeclass Node: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right# function to convert the array to BST# and return the root of the created treedef sortedArrayToBST(nums: List[int]) -> Node: # if the array is empty return None if not nums: return None n = len(nums) mid = n // 2 root = Node(nums[mid]) # initializing queue q = Queue() # push the root and its indices to the queue q.put((root, (0, mid-1))) q.put((root, (mid+1, n-1))) while not q.empty(): # get the front element from the queue curr = q.get() # get the parent node and its indices parent = curr[0] left = curr[1][0] right = curr[1][1] # if there are elements to process and parent node is not None if left <= right and parent is not None: mid = (left + right) // 2 child = Node(nums[mid]) # set the child node as left or right child of the parent node if nums[mid] < parent.val: parent.left = child else: parent.right = child # push the left and right child and their indices to the queue q.put((child, (left, mid-1))) q.put((child, (mid+1, right))) return root# function to print the preorder traversal# of the constructed BSTdef printBST(root: Node) -> None: if root is None: return print(root.val, end=" ") printBST(root.left) printBST(root.right)# Driver program to test the above functionif __name__ == "__main__": # create a sorted array nums = [1, 2, 3, 4, 5, 6, 7] root = sortedArrayToBST(nums) printBST(root) |
C#
// C# code additionusing System;using System.Collections.Generic;// structure of the tree nodeclass Node { public int val; public Node left; public Node right; public Node(int val) { this.val = val; left = null; right = null; }}class Program { // function to convert the array to BST // and return the root of the created tree static Node SortedArrayToBST(List<int> nums) { // if the array is empty return null if (nums.Count == 0) { return null; } int n = nums.Count; int mid = n / 2; Node root = new Node(nums[mid]); // initializing queue Queue<Tuple<Node, Tuple<int, int> > > q = new Queue<Tuple<Node, Tuple<int, int> > >(); // push the root and its indices to the queue q.Enqueue(new Tuple<Node, Tuple<int, int> >( root, new Tuple<int, int>(0, mid - 1))); q.Enqueue(new Tuple<Node, Tuple<int, int> >( root, new Tuple<int, int>(mid + 1, n - 1))); while (q.Count != 0) { // get the front element from the queue Tuple<Node, Tuple<int, int> > curr = q.Dequeue(); // get the parent node and its indices Node parent = curr.Item1; int left = curr.Item2.Item1; int right = curr.Item2.Item2; // if there are elements to process and parent // node is not null if (left <= right && parent != null) { int Mid = (left + right) / 2; Node child = new Node(nums[Mid]); // set the child node as left or right child // of the parent node if (nums[Mid] < parent.val) { parent.left = child; } else { parent.right = child; } // push the left and right child and their // indices to the queue q.Enqueue(new Tuple<Node, Tuple<int, int> >( child, new Tuple<int, int>(left, Mid - 1))); q.Enqueue(new Tuple<Node, Tuple<int, int> >( child, new Tuple<int, int>(Mid + 1, right))); } } return root; } // function to print the preorder traversal // of the constructed BST static void PrintBST(Node root) { if (root == null) return; Console.Write(root.val + " "); PrintBST(root.left); PrintBST(root.right); } // Driver program to test the above function static void Main(string[] args) { // create a sorted array List<int> nums = new List<int>{ 1, 2, 3, 4, 5, 6, 7 }; // construct the BST from the array Node root = SortedArrayToBST(nums); // print the preorder traversal of the BST PrintBST(root); // Output: 4 2 1 3 6 5 7 }}// The code is contributed by Arushi Goel. |
Javascript
class Node { constructor(val) { this.val = val; this.left = null; this.right = null; }}// function to convert the array to BST// and return the root of the created treefunction sortedArrayToBST(nums) {// if the array is empty return NULL if (nums.length === 0) { return null; } const mid = Math.floor(nums.length / 2); const root = new Node(nums[mid]); // initializing queue const q = [[root, [0, mid - 1]], [root, [mid + 1, nums.length - 1]]]; while (q.length > 0) { const [parent, [left, right]] = q.shift(); // if there are elements to process and parent node is not NULL if (left <= right && parent != null) { const mid = Math.floor((left + right) / 2); const child = new Node(nums[mid]); // set the child node as left or right child of the parent node if (nums[mid] < parent.val) { parent.left = child; } else { parent.right = child; } // push the left and right child and their indices to the queue q.push([child, [left, mid - 1]]); q.push([child, [mid + 1, right]]); } } return root;}// function to print the preorder traversal// of the constructed BSTfunction printBST(root) { if (root === null) { return; } console.log(root.val + " "); printBST(root.left); printBST(root.right);}// Driver program to test the above functionconst nums = [1, 2, 3, 4, 5, 6, 7];const root = sortedArrayToBST(nums);printBST(root); // Output: 4 2 1 3 6 5 7 |
Output
4 2 1 3 6 5 7
Time Complexity: O(N), where N is the number of elements in array.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
