Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree.
Examples
Example 1
Input:
10
/ \
2 7
/ \
8 4
Output:
8
/ \
4 10
/ \
2 7
Example 2
Input:
10
/ \
30 15
/ \
20 5
Output:
15
/ \
10 20
/ \
5 30
Solution:
Following is a 3 step solution for converting Binary tree to Binary Search Tree.
- Create a temp array arr[] that stores inorder traversal of the tree. This step takes O(n) time.
- Sort the temp array arr[]. Time complexity of this step depends upon the sorting algorithm. In the following implementation, Quick Sort is used which takes (n^2) time. This can be done in O(nLogn) time using Heap Sort or Merge Sort.
- Again do inorder traversal of tree and copy array elements to tree nodes one by one. This step takes O(n) time.
Following is the implementation of the above approach. The main function to convert is highlighted in the following code.
Implementation:
C++
/* A program to convert Binary Tree to Binary Search Tree */#include <iostream>using namespace std;/* A binary tree node structure */struct node { int data; struct node* left; struct node* right;};/* A helper function that stores inorder traversal of a tree rooted with node */void storeInorder(struct node* node, int inorder[], int* index_ptr){ // Base Case if (node == NULL) return; /* first store the left subtree */ storeInorder(node->left, inorder, index_ptr); /* Copy the root's data */ inorder[*index_ptr] = node->data; (*index_ptr)++; // increase index for next entry /* finally store the right subtree */ storeInorder(node->right, inorder, index_ptr);}/* A helper function to count nodes in a Binary Tree */int countNodes(struct node* root){ if (root == NULL) return 0; return countNodes(root->left) + countNodes(root->right) + 1;}// Following function is needed for library function qsort()int compare(const void* a, const void* b){ return (*(int*)a - *(int*)b);}/* A helper function that copies contents of arr[] to Binary Tree. This function basically does Inorder traversal of Binary Tree and one by one copy arr[] elements to Binary Tree nodes */void arrayToBST(int* arr, struct node* root, int* index_ptr){ // Base Case if (root == NULL) return; /* first update the left subtree */ arrayToBST(arr, root->left, index_ptr); /* Now update root's data and increment index */ root->data = arr[*index_ptr]; (*index_ptr)++; /* finally update the right subtree */ arrayToBST(arr, root->right, index_ptr);}// This function converts a given Binary Tree to BSTvoid binaryTreeToBST(struct node* root){ // base case: tree is empty if (root == NULL) return; /* Count the number of nodes in Binary Tree so that we know the size of temporary array to be created */ int n = countNodes(root); // Create a temp array arr[] and store inorder // traversal of tree in arr[] int* arr = new int[n]; int i = 0; storeInorder(root, arr, &i); // Sort the array using library function for quick sort qsort(arr, n, sizeof(arr[0]), compare); // Copy array elements back to Binary Tree i = 0; arrayToBST(arr, root, &i); // delete dynamically allocated memory to // avoid memory leak delete[] arr;}/* Utility function to create a new Binary Tree node */struct node* newNode(int data){ struct node* temp = new struct node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp;}/* Utility function to print inorder traversal of Binary Tree */void printInorder(struct node* node){ if (node == NULL) return; /* first recur on left child */ printInorder(node->left); /* then print the data of node */ cout <<" "<< node->data; /* now recur on right child */ printInorder(node->right);}/* Driver function to test above functions */int main(){ struct node* root = NULL; /* Constructing tree given in the above figure 10 / \ 30 15 / \ 20 5 */ root = newNode(10); root->left = newNode(30); root->right = newNode(15); root->left->left = newNode(20); root->right->right = newNode(5); // convert Binary Tree to BST binaryTreeToBST(root); cout <<"Following is Inorder Traversal of the converted BST:" << endl ; printInorder(root); return 0;} // This code is contributed by shivanisinghss2110 |
C
/* A program to convert Binary Tree to Binary Search Tree */#include <stdio.h>#include <stdlib.h>/* A binary tree node structure */struct node { int data; struct node* left; struct node* right;};/* A helper function that stores inorder traversal of a tree rootedwith node */void storeInorder(struct node* node, int inorder[], int* index_ptr){ // Base Case if (node == NULL) return; /* first store the left subtree */ storeInorder(node->left, inorder, index_ptr); /* Copy the root's data */ inorder[*index_ptr] = node->data; (*index_ptr)++; // increase index for next entry /* finally store the right subtree */ storeInorder(node->right, inorder, index_ptr);}/* A helper function to count nodes in a Binary Tree */int countNodes(struct node* root){ if (root == NULL) return 0; return countNodes(root->left) + countNodes(root->right) + 1;}// Following function is needed for library function qsort()int compare(const void* a, const void* b){ return (*(int*)a - *(int*)b);}/* A helper function that copies contents of arr[] to Binary Tree.This function basically does Inorder traversal of Binary Tree andone by one copy arr[] elements to Binary Tree nodes */void arrayToBST(int* arr, struct node* root, int* index_ptr){ // Base Case if (root == NULL) return; /* first update the left subtree */ arrayToBST(arr, root->left, index_ptr); /* Now update root's data and increment index */ root->data = arr[*index_ptr]; (*index_ptr)++; /* finally update the right subtree */ arrayToBST(arr, root->right, index_ptr);}// This function converts a given Binary Tree to BSTvoid binaryTreeToBST(struct node* root){ // base case: tree is empty if (root == NULL) return; /* Count the number of nodes in Binary Tree so that we know the size of temporary array to be created */ int n = countNodes(root); // Create a temp array arr[] and store inorder traversal of tree in arr[] int* arr = new int[n]; int i = 0; storeInorder(root, arr, &i); // Sort the array using library function for quick sort qsort(arr, n, sizeof(arr[0]), compare); // Copy array elements back to Binary Tree i = 0; arrayToBST(arr, root, &i); // delete dynamically allocated memory to avoid memory leak delete[] arr;}/* Utility function to create a new Binary Tree node */struct node* newNode(int data){ struct node* temp = new struct node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp;}/* Utility function to print inorder traversal of Binary Tree */void printInorder(struct node* node){ if (node == NULL) return; /* first recur on left child */ printInorder(node->left); /* then print the data of node */ printf("%d ", node->data); /* now recur on right child */ printInorder(node->right);}/* Driver function to test above functions */int main(){ struct node* root = NULL; /* Constructing tree given in the above figure 10 / \ 30 15 / \ 20 5 */ root = newNode(10); root->left = newNode(30); root->right = newNode(15); root->left->left = newNode(20); root->right->right = newNode(5); // convert Binary Tree to BST binaryTreeToBST(root); printf("Following is Inorder Traversal of the converted BST: \n"); printInorder(root); return 0;} |
Java
/* A program to convert Binary Tree to Binary Search Tree */import java.util.*;public class GFG{ /* A binary tree node structure */ static class Node { int data; Node left; Node right; }; // index pointer to pointer to the array index static int index; /* A helper function that stores inorder traversal of a tree rooted with node */ static void storeInorder(Node node, int inorder[]) { // Base Case if (node == null) return; /* first store the left subtree */ storeInorder(node.left, inorder); /* Copy the root's data */ inorder[index] = node.data; index++; // increase index for next entry /* finally store the right subtree */ storeInorder(node.right, inorder); } /* A helper function to count nodes in a Binary Tree */ static int countNodes(Node root) { if (root == null) return 0; return countNodes(root.left) + countNodes(root.right) + 1; } /* A helper function that copies contents of arr[] to Binary Tree. This function basically does Inorder traversal of Binary Tree and one by one copy arr[] elements to Binary Tree nodes */ static void arrayToBST(int[] arr, Node root) { // Base Case if (root == null) return; /* first update the left subtree */ arrayToBST(arr, root.left); /* Now update root's data and increment index */ root.data = arr[index]; index++; /* finally update the right subtree */ arrayToBST(arr, root.right); } // This function converts a given Binary Tree to BST static void binaryTreeToBST(Node root) { // base case: tree is empty if (root == null) return; /* Count the number of nodes in Binary Tree so that we know the size of temporary array to be created */ int n = countNodes(root); // Create a temp array arr[] and store inorder traversal of tree in arr[] int arr[] = new int[n]; storeInorder(root, arr); // Sort the array using library function for quick sort Arrays.sort(arr); // Copy array elements back to Binary Tree index = 0; arrayToBST(arr, root); } /* Utility function to create a new Binary Tree node */ static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = null; temp.right = null; return temp; } /* Utility function to print inorder traversal of Binary Tree */ static void printInorder(Node node) { if (node == null) return; /* first recur on left child */ printInorder(node.left); /* then print the data of node */ System.out.print(node.data + " "); /* now recur on right child */ printInorder(node.right); } /* Driver function to test above functions */ public static void main(String args[]) { Node root = null; /* Constructing tree given in the above figure 10 / \ 30 15 / \ 20 5 */ root = newNode(10); root.left = newNode(30); root.right = newNode(15); root.left.left = newNode(20); root.right.right = newNode(5); // convert Binary Tree to BST binaryTreeToBST(root); System.out.println("Following is Inorder Traversal of the converted BST: "); printInorder(root); }}// This code is contributed by adityapande88. |
Python3
# Program to convert binary tree to BST# A binary tree nodeclass Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None# Helper function to store the inorder traversal of a treedef storeInorder(root, inorder): # Base Case if root is None: return # First store the left subtree storeInorder(root.left, inorder) # Copy the root's data inorder.append(root.data) # Finally store the right subtree storeInorder(root.right, inorder)# A helper function to count nodes in a binary treedef countNodes(root): if root is None: return 0 return countNodes(root.left) + countNodes(root.right) + 1# Helper function that copies contents of sorted array # to Binary treedef arrayToBST(arr, root): # Base Case if root is None: return # First update the left subtree arrayToBST(arr, root.left) # now update root's data delete the value from array root.data = arr[0] arr.pop(0) # Finally update the right subtree arrayToBST(arr, root.right)# This function converts a given binary tree to BSTdef binaryTreeToBST(root): # Base Case: Tree is empty if root is None: return # Count the number of nodes in Binary Tree so that # we know the size of temporary array to be created n = countNodes(root) # Create the temp array and store the inorder traversal # of tree arr = [] storeInorder(root, arr) # Sort the array arr.sort() # copy array elements back to binary tree arrayToBST(arr, root)# Print the inorder traversal of the treedef printInorder(root): if root is None: return printInorder(root.left) print (root.data,end=" ") printInorder(root.right)# Driver program to test above functionroot = Node(10)root.left = Node(30)root.right = Node(15)root.left.left = Node(20)root.right.right = Node(5)# Convert binary tree to BST binaryTreeToBST(root)print ("Following is the inorder traversal of the converted BST")printInorder(root)# This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
using System;public class Node{ public int data; public Node left; public Node right;}public class GFG{ // index pointer to pointer to the array index static int index; /* A helper function that stores inorder traversal of a tree rooted with node */ static void storeInorder(Node node, int[] inorder) { // Base Case if (node == null) return; /* first store the left subtree */ storeInorder(node.left, inorder); /* Copy the root's data */ inorder[index] = node.data; index++; // increase index for next entry /* finally store the right subtree */ storeInorder(node.right, inorder); } /* A helper function to count nodes in a Binary Tree */ static int countNodes(Node root) { if (root == null) return 0; return countNodes(root.left) + countNodes(root.right) + 1; } /* A helper function that copies contents of arr[] to Binary Tree. This function basically does Inorder traversal of Binary Tree and one by one copy arr[] elements to Binary Tree nodes */ static void arrayToBST(int[] arr, Node root) { // Base Case if (root == null) return; /* first update the left subtree */ arrayToBST(arr, root.left); /* Now update root's data and increment index */ root.data = arr[index]; index++; /* finally update the right subtree */ arrayToBST(arr, root.right); } // This function converts a given Binary Tree to BST static void binaryTreeToBST(Node root) { // base case: tree is empty if (root == null) return; /* Count the number of nodes in Binary Tree so that we know the size of temporary array to be created */ int n = countNodes(root); // Create a temp array arr[] and store inorder traversal of tree in arr[] int[] arr = new int[n]; storeInorder(root, arr); // Sort the array using library function for quick sort Array.Sort(arr); // Copy array elements back to Binary Tree index = 0; arrayToBST(arr, root); } /* Utility function to create a new Binary Tree node */ static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = null; temp.right = null; return temp; } /* Utility function to print inorder traversal of Binary Tree */ static void printInorder(Node node) { if (node == null) return; /* first recur on left child */ printInorder(node.left); /* then print the data of node */ Console.Write(node.data + " "); /* now recur on right child */ printInorder(node.right); } /* Driver function to test above functions */ static public void Main (){ Node root = null; /* Constructing tree given in the above figure 10 / \ 30 15 / \ 20 5 */ root = newNode(10); root.left = newNode(30); root.right = newNode(15); root.left.left = newNode(20); root.right.right = newNode(5); // convert Binary Tree to BST binaryTreeToBST(root); Console.WriteLine("Following is Inorder Traversal of the converted BST: "); printInorder(root); }}// This code is contributed by avanitrachhadiya2155 |
Javascript
<script> /* A program to convert Binary Tree to Binary Search Tree */ class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // index pointer to pointer to the array index let index = 0; /* Utility function to create a new Binary Tree node */ function newNode(data) { let temp = new Node(data); return temp; } /* Utility function to print inorder traversal of Binary Tree */ function printInorder(node) { if (node == null) return; /* first recur on left child */ printInorder(node.left); /* then print the data of node */ document.write(node.data + " "); /* now recur on right child */ printInorder(node.right); } /* A helper function that copies contents of arr[] to Binary Tree. This function basically does Inorder traversal of Binary Tree and one by one copy arr[] elements to Binary Tree nodes */ function arrayToBST(arr, root) { // Base Case if (root == null) return; /* first update the left subtree */ arrayToBST(arr, root.left); /* Now update root's data and increment index */ root.data = arr[index]; index++; /* finally update the right subtree */ arrayToBST(arr, root.right); } /* A helper function that stores inorder traversal of a tree rooted with node */ function storeInorder(node, inorder) { // Base Case if (node == null) return inorder; /* first store the left subtree */ storeInorder(node.left, inorder); /* Copy the root's data */ inorder[index] = node.data; index++; // increase index for next entry /* finally store the right subtree */ storeInorder(node.right, inorder); } /* A helper function to count nodes in a Binary Tree */ function countNodes(root) { if (root == null) return 0; return countNodes(root.left) + countNodes(root.right) + 1; } // This function converts a given Binary Tree to BST function binaryTreeToBST(root) { // base case: tree is empty if (root == null) return; /* Count the number of nodes in Binary Tree so that we know the size of temporary array to be created */ let n = countNodes(root); // Create a temp array arr[] and store // inorder traversal of tree in arr[] let arr = new Array(n); arr.fill(0); storeInorder(root, arr); // Sort the array using library function for quick sort arr.sort(function(a, b){return a - b}); // Copy array elements back to Binary Tree index = 0; arrayToBST(arr, root); } let root = null; /* Constructing tree given in the above figure 10 / \ 30 15 / \ 20 5 */ root = newNode(10); root.left = newNode(30); root.right = newNode(15); root.left.left = newNode(20); root.right.right = newNode(5); // convert Binary Tree to BST binaryTreeToBST(root); document.write( "Following is Inorder Traversal of the converted BST: "+ "</br>"); printInorder(root); </script> |
Output
Following is the inorder traversal of the converted BST 5 10 15 20 30
Complexity Analysis:
- Time Complexity: O(nlogn). This is the complexity of the sorting algorithm which we are using after first in-order traversal, rest of the operations take place in linear time.
- Auxiliary Space: O(n). Use of data structure ‘array’ to store in-order traversal.
Another approach :- Using Inorder Traversal and Vector Sorting
In this approach, we will first perform an inorder traversal of the binary tree and store the nodes in a vector. After that, we will sort the vector in ascending order, and then use the sorted vector to construct a binary search tree.
Define a struct for a binary tree node with a value, left and right pointers.
Implement an inorder traversal of the binary tree to store the nodes in a vector. In this implementation, a vector of TreeNode* is used to store the nodes in inorder traversal order. The function takes in a TreeNode* root and a reference to the vector of TreeNode* nodes.
Implement a function to construct a binary search tree from the sorted vector of TreeNode* nodes. The function takes in the vector of TreeNode* nodes, start index, and end index of the vector. It recursively constructs the binary search tree by taking the middle element of the vector as the root, and then constructing the left and right subtrees recursively.
Implement a function to convert a binary tree to a binary search tree. This function takes in the root of the binary tree and returns the root of the binary search tree. It first calls the inorder traversal function to store the nodes of the binary tree in a vector, then sorts the vector of TreeNode* based on the values of the nodes using a lambda function, and finally calls the function to construct the binary search tree.
Implement a function to print the inorder traversal of a binary tree. This function takes in the root of the binary tree and prints its inorder traversal.
In the driver code, create a binary tree with some nodes, print its inorder traversal, convert it to a binary search tree, print the inorder traversal of the binary search tree, and free the dynamically allocated memory for the nodes.
Here’s the C++ code:
C++
#include <iostream>#include <vector>#include <algorithm>using namespace std;// Definition for a binary tree node.struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};// Inorder traversal to store the nodes in a vectorvoid inorder(TreeNode* root, vector<TreeNode*>& nodes) { if (root == NULL) { return; } inorder(root->left, nodes); nodes.push_back(root); inorder(root->right, nodes);}// Function to construct a binary search tree from a sorted vectorTreeNode* constructBST(vector<TreeNode*>& nodes, int start, int end) { if (start > end) { return NULL; } int mid = (start + end) / 2; TreeNode* root = nodes[mid]; root->left = constructBST(nodes, start, mid - 1); root->right = constructBST(nodes, mid + 1, end); return root;}// Function to convert a binary tree to a binary search treeTreeNode* convertToBST(TreeNode* root) { vector<TreeNode*> nodes; inorder(root, nodes); sort(nodes.begin(), nodes.end(), [](const TreeNode* a, const TreeNode* b) { return a->val < b->val; }); return constructBST(nodes, 0, nodes.size() - 1);}// Function to print the inorder traversal of a binary treevoid printInorder(TreeNode* root) { if (root == NULL) { return; } printInorder(root->left); cout << root->val << " "; printInorder(root->right);}// Driver codeint main() { // Example binary tree TreeNode* root = new TreeNode(10); root->left = new TreeNode(30); root->right = new TreeNode(15); root->left->left = new TreeNode(20); root->left->right = new TreeNode(5); // Convert binary tree to binary search tree TreeNode* bst = convertToBST(root); cout <<"Following is Inorder Traversal of the converted BST:" << endl ; printInorder(bst); cout << endl; return 0;} |
Java
import java.util.ArrayList;import java.util.Collections;class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }}public class Main { public static void main(String[] args) { // Example binary tree TreeNode root = new TreeNode(10); root.left = new TreeNode(30); root.right = new TreeNode(15); root.left.left = new TreeNode(20); root.left.right = new TreeNode(5); // Convert binary tree to binary search tree TreeNode bst = convertToBST(root); System.out.println("Following is Inorder Traversal of the converted BST:"); printInorder(bst); } // Inorder traversal to store the nodes in an ArrayList public static void inorder(TreeNode root, ArrayList<TreeNode> nodes) { if (root == null) { return; } inorder(root.left, nodes); nodes.add(root); inorder(root.right, nodes); } // Function to construct a binary search tree from a sorted ArrayList public static TreeNode constructBST(ArrayList<TreeNode> nodes, int start, int end) { if (start > end) { return null; } int mid = (start + end) / 2; TreeNode root = nodes.get(mid); root.left = constructBST(nodes, start, mid - 1); root.right = constructBST(nodes, mid + 1, end); return root; } // Function to convert a binary tree to a binary search tree public static TreeNode convertToBST(TreeNode root) { ArrayList<TreeNode> nodes = new ArrayList<>(); inorder(root, nodes); Collections.sort(nodes, (a, b) -> a.val - b.val); return constructBST(nodes, 0, nodes.size() - 1); } // Function to print the inorder traversal of a binary tree public static void printInorder(TreeNode root) { if (root == null) { return; } printInorder(root.left); System.out.print(root.val + " "); printInorder(root.right); }} |
Python3
# Definition for a binary tree node.class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None# Inorder traversal to store the nodes in a listdef inorder(root, nodes): if root is None: return inorder(root.left, nodes) nodes.append(root) inorder(root.right, nodes)# Function to construct a binary search tree from a sorted listdef constructBST(nodes, start, end): if start > end: return None mid = (start + end) // 2 root = nodes[mid] root.left = constructBST(nodes, start, mid - 1) root.right = constructBST(nodes, mid + 1, end) return root# Function to convert a binary tree to a binary search treedef convertToBST(root): nodes = [] inorder(root, nodes) nodes.sort(key=lambda node: node.val) return constructBST(nodes, 0, len(nodes) - 1)# Function to print the inorder traversal of a binary treedef printInorder(root): if root is None: return printInorder(root.left) print(root.val, end=" ") printInorder(root.right)# Driver codeif __name__ == "__main__": # Example binary tree root = TreeNode(10) root.left = TreeNode(30) root.right = TreeNode(15) root.left.left = TreeNode(20) root.left.right = TreeNode(5) # Convert binary tree to binary search tree bst = convertToBST(root) print("Following is Inorder Traversal of the converted BST:") printInorder(bst) print() # by phasing17 |
C#
using System;using System.Collections.Generic;public class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; }}public class GFG{ public static void Main(string[] args) { // Example binary tree TreeNode root = new TreeNode(10); root.left = new TreeNode(30); root.right = new TreeNode(15); root.left.left = new TreeNode(20); root.left.right = new TreeNode(5); // Convert binary tree to binary search tree TreeNode bst = ConvertToBST(root); Console.WriteLine("Following is Inorder Traversal of the converted BST:"); PrintInorder(bst); } // Inorder traversal to store the nodes in a List public static void Inorder(TreeNode root, List<TreeNode> nodes) { if (root == null) { return; } Inorder(root.left, nodes); nodes.Add(root); Inorder(root.right, nodes); } // Function to construct a binary search tree from a sorted List public static TreeNode ConstructBST(List<TreeNode> nodes, int start, int end) { if (start > end) { return null; } int mid = (start + end) / 2; TreeNode root = nodes[mid]; root.left = ConstructBST(nodes, start, mid - 1); root.right = ConstructBST(nodes, mid + 1, end); return root; } // Function to convert a binary tree to a binary search tree public static TreeNode ConvertToBST(TreeNode root) { List<TreeNode> nodes = new List<TreeNode>(); Inorder(root, nodes); nodes.Sort((a, b) => a.val - b.val); return ConstructBST(nodes, 0, nodes.Count - 1); } // Function to print the inorder traversal of a binary tree public static void PrintInorder(TreeNode root) { if (root == null) { return; } PrintInorder(root.left); Console.Write(root.val + " "); PrintInorder(root.right); }}// by phasing17 |
Javascript
// Definition for a binary tree node.class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}// Inorder traversal to store the nodes in an arrayfunction inorder(root, nodes) { if (root === null) { return; } inorder(root.left, nodes); nodes.push(root); inorder(root.right, nodes);}// Function to construct a binary search tree from a sorted arrayfunction constructBST(nodes, start, end) { if (start > end) { return null; } const mid = Math.floor((start + end) / 2); const root = nodes[mid]; root.left = constructBST(nodes, start, mid - 1); root.right = constructBST(nodes, mid + 1, end); return root;}// Function to convert a binary tree to a binary search treefunction convertToBST(root) { const nodes = []; inorder(root, nodes); nodes.sort((a, b) => a.val - b.val); return constructBST(nodes, 0, nodes.length - 1);}// Function to print the inorder traversal of a binary tree in one linefunction printInorder(root) { const result = []; function inorderTraversal(node) { if (node === null) { return; } inorderTraversal(node.left); result.push(node.val); inorderTraversal(node.right); } inorderTraversal(root); console.log(result.join(' '));}// Driver code// Example binary treeconst root = new TreeNode(10);root.left = new TreeNode(30);root.right = new TreeNode(15);root.left.left = new TreeNode(20);root.left.right = new TreeNode(5);// Convert binary tree to binary search treeconst bst = convertToBST(root);console.log("Following is Inorder Traversal of the converted BST:");printInorder(bst);// this code is contributed by uttamdp_10 |
Output
Following is Inorder Traversal of the converted BST: 5 10 15 20 30
Time Complexity: O(nlogn).
Auxiliary Space: O(n).
We will be covering another method for this problem which converts the tree using O(height of the tree) extra space.
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!
