Given an unsorted vector arr, the task is to create a balanced binary search tree using the elements of the array.
Note: There can be more than one balanced BST. Forming any is acceptable
Examples:
Input: arr[] = { 2, 1, 3}
Output: 2 1 3
Explanation: The tree formed is show below. The preorder traversal is 2 1 3
2
/ \
1 3Input: arr[] = {4, 3, 1, 2}
Output: 2 1 3 4
Explanation: The tree formed is
2
/ \
1 3
\
4
Another possible option can provide preorder traversal is 3 2 1 4
Approach: To solve this problem, follow the below steps:
- Firstly, we will sort the vector using the sort function.
- Now, get the Middle of the vector and make it root.
- Recursively do the same for the left half and the right half.
- Get the middle of the left half and make it the left child of the root created in step 2.
- Get the middle of the right half and make it the right child of the root created in step 2.
Below is the implementation of the above approach:
C++
// C++ program to print BST in given range#include <bits/stdc++.h>using namespace std;// Node of Binary Search Treeclass Node {public: Node* left; int data; Node* right; Node(int d) { data = d; left = right = NULL; }};// A function that constructs Balanced// Binary Search Tree from a vectorNode* createBST(vector<int> v, int start, int end){ sort(v.begin(), v.end()); // Base Case if (start > end) return NULL; // Get the middle element and make it root int mid = (start + end) / 2; Node* root = new Node(v[mid]); // Recursively construct the left subtree // and make it left child of root root->left = createBST(v, start, mid - 1); // Recursively construct the right subtree // and make it right child of root root->right = createBST(v, mid + 1, end); return root;}vector<int> preNode, vec;// A utility function to print// preorder traversal of BSTvector<int> preOrder(Node* node){ // Root Left Right if (node == NULL) { return vec; } preNode.push_back(node->data); preOrder(node->left); preOrder(node->right); return preNode;}// Driver Codeint main(){ vector<int> v = { 4, 3, 1, 2 }; Node* root = createBST(v, 0, v.size() - 1); vector<int> ans = preOrder(root); for (auto i : ans) { cout << i << " "; } return 0;} |
Java
// Java program for the above approachimport java.util.*;// Node of Binary Search Treeclass Node { Node left; int data; Node right; Node(int d) { data = d; left = right = null; }}class Main { static List<Integer> preNode = new ArrayList<>(); static List<Integer> vec = new ArrayList<>(); // A function that constructs Balanced // Binary Search Tree from a vector static Node createBST(List<Integer> v, int start, int end) { Collections.sort(v); // Base Case if (start > end) return null; // Get the middle element and make it root int mid = (start + end) / 2; Node root = new Node(v.get(mid)); // Recursively construct the left subtree // and make it left child of root root.left = createBST(v, start, mid - 1); // Recursively construct the right subtree // and make it right child of root root.right = createBST(v, mid + 1, end); return root; } // A utility function to print // preorder traversal of BST static List<Integer> preOrder(Node node) { // Root Left Right if (node == null) { return vec; } preNode.add(node.data); preOrder(node.left); preOrder(node.right); return preNode; } // Driver Code public static void main(String[] args) { List<Integer> v = Arrays.asList(4, 3, 1, 2); Node root = createBST(v, 0, v.size() - 1); List<Integer> ans = preOrder(root); for (int i : ans) { System.out.print(i + " "); } }}// This code is contributed by codebraxnzt |
C#
// C# Program for the above approachusing System;using System.Collections.Generic;using System.Linq;// Node of Binary Search Treeclass Node{ public Node left; public int data; public Node right; public Node(int d) { data = d; left = right = null; }}class MainClass{ static List<int> preNode = new List<int>(); static List<int> vec = new List<int>(); // A function that constructs Balanced // Binary Search Tree from a vector static Node createBST(List<int> v, int start, int end) { v.Sort(); // Base Case if (start > end) return null; // Get the middle element and make it root int mid = (start + end) / 2; Node root = new Node(v[mid]); // Recursively construct the left subtree // and make it left child of root root.left = createBST(v, start, mid - 1); // Recursively construct the right subtree // and make it right child of root root.right = createBST(v, mid + 1, end); return root; } // A utility function to print // preorder traversal of BST static List<int> preOrder(Node node) { // Root Left Right if (node == null) { return vec; } preNode.Add(node.data); preOrder(node.left); preOrder(node.right); return preNode; } // Driver Code public static void Main(string[] args) { List<int> v = new List<int> { 4, 3, 1, 2 }; Node root = createBST(v, 0, v.Count - 1); List<int> ans = preOrder(root); foreach (int i in ans) { Console.Write(i + " "); } }}// This code is contributed by adityashatmfh |
Output
PreOrder Traversal of constructed BST 4 2 1 3 6 5 7
Time Complexity: O(N * logN)
Auxiliary Space: O(N) to create the tree
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!
