Construct a Binary Tree from the given Binary Search Tree such that it’s level order traversal outputs sorted data.
Examples:
Input:
Output: 1 2 3
Input:
Output: 1 2 3 4 5
Approach:
- Perform the inorder traversal of the given Binary Search Tree.
- Add each node in level order to the Binary Tree.
- Finally, print the level order traversal of the created Binary Tree.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Structure to hold the contents// of the new nodestruct node { int data; node *left, *right;}* root1 = NULL;// Helper function to add and// return the newly added nodenode* add(int data){ node* newnode = new node; newnode->data = data; newnode->left = newnode->right = NULL; return newnode;}// Function to add a node to the// Binary Tree in the level ordervoid addinBT(int data){ // If it is the first node // to be added then make // it the root node if (root1 == NULL) root1 = add(data); else { queue<node*> Q; Q.push(root1); while (!Q.empty()) { // Get and remove the front node* temp = Q.front(); Q.pop(); // If the left child of the current // node is null then create the new // node here and break if (temp->left == NULL) { temp->left = add(data); break; } else Q.push(temp->left); // If the right child of the current // node is null then create the new // node here and break if (temp->right == NULL) { temp->right = add(data); break; } else Q.push(temp->right); } }}// Function to add a node to// the Binary Search treenode* addinBST(node* root, int data){ // If the current node is null // then create a new node here // with the given data if (root == NULL) root = add(data); // If the data is smaller than the // current node's data then recur // for the left sub-tree else if (data < root->data) root->left = addinBST(root->left, data); // Else recur for the right sub-tree else root->right = addinBST(root->right, data); return root;}// Function to perform a level order// insertion in the Binary Tree from// the given Binary Search treevoid addinorder(node* root){ if (root == NULL) return; addinorder(root->left); addinBT(root->data); addinorder(root->right);}// Function to print the level order// traversal of the binary treevoid printlvl(){ queue<node*> Q; // Push root to the queue Q.push(root1); while (!Q.empty()) { // Get the front node* temp = Q.front(); // Remove the front Q.pop(); // Print the data cout << temp->data << " "; // Push the left child if (temp->left != NULL) Q.push(temp->left); // Push the right child if (temp->right != NULL) Q.push(temp->right); }}// Driver codeint main(){ // Create the Binary Search Tree node* root = NULL; root = addinBST(root, 1); root = addinBST(root, 2); root = addinBST(root, 3); root = addinBST(root, 4); root = addinBST(root, 5); // Add nodes of the Binary Search // Tree to the Binary Tree addinorder(root); // Print the level order traversal // of the Binary Tree printlvl(); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Structure to hold the contents// of the new nodestatic class node { int data; node left, right;}static node root1 = null;// Helper function to add and// return the newly added nodestatic node add(int data){ node newnode = new node(); newnode.data = data; newnode.left = newnode.right = null; return newnode;}// Function to add a node to the// Binary Tree in the level orderstatic void addinBT(int data){ // If it is the first node // to be added then make // it the root node if (root1 == null) root1 = add(data); else { Queue<node> Q = new LinkedList<>(); Q.add(root1); while (!Q.isEmpty()) { // Get and remove the front node temp = Q.peek(); Q.remove(); // If the left child of the current // node is null then create the new // node here and break if (temp.left == null) { temp.left = add(data); break; } else Q.add(temp.left); // If the right child of the current // node is null then create the new // node here and break if (temp.right == null) { temp.right = add(data); break; } else Q.add(temp.right); } }}// Function to add a node to// the Binary Search treestatic node addinBST(node root, int data){ // If the current node is null // then create a new node here // with the given data if (root == null) root = add(data); // If the data is smaller than the // current node's data then recur // for the left sub-tree else if (data < root.data) root.left = addinBST(root.left, data); // Else recur for the right sub-tree else root.right = addinBST(root.right, data); return root;}// Function to perform a level order// insertion in the Binary Tree from// the given Binary Search treestatic void addinorder(node root){ if (root == null) return; addinorder(root.left); addinBT(root.data); addinorder(root.right);}// Function to print the level order// traversal of the binary treestatic void printlvl(){ Queue<node> Q = new LinkedList<>(); // Push root to the queue Q.add(root1); while (!Q.isEmpty()) { // Get the front node temp = Q.peek(); // Remove the front Q.remove(); // Print the data System.out.print(temp.data + " "); // Push the left child if (temp.left != null) Q.add(temp.left); // Push the right child if (temp.right != null) Q.add(temp.right); }}// Driver codepublic static void main(String[] args){ // Create the Binary Search Tree node root = null; root = addinBST(root, 1); root = addinBST(root, 2); root = addinBST(root, 3); root = addinBST(root, 4); root = addinBST(root, 5); // Add nodes of the Binary Search // Tree to the Binary Tree addinorder(root); // Print the level order traversal // of the Binary Tree printlvl();}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Structure to hold the contents # of the new node class add: # Constructor to create a new node def __init__(self, data): self.data = data self.left = self.right = Noneroot1 = None# Function to add a node to the # Binary Tree in the level order def addinBT(data): global root1 # If it is the first node # to be added then make # it the root node if (root1 == None): root1 = add(data) else: Q = [root1] while (len(Q)): # Get and remove the front temp = Q[0] Q.pop(0) # If the left child of the current # node is None then create the new # node here and break if (temp.left == None): temp.left = add(data) break else: Q.append(temp.left) # If the right child of the current # node is None then create the new # node here and break if (temp.right == None): temp.right = add(data) break else: Q.append(temp.right) # Function to add a node to # the Binary Search tree def addinBST( root, data): # If the current node is None # then create a new node here # with the given data if (root == None): root = add(data) # If the data is smaller than the # current node's data then recur # for the left sub-tree elif (data < root.data): root.left = addinBST(root.left, data) # Else recur for the right sub-tree else: root.right = addinBST(root.right, data) return root # Function to perform a level order # insertion in the Binary Tree from # the given Binary Search tree def addinorder( root): if (root == None): return addinorder(root.left) addinBT(root.data) addinorder(root.right) # Function to print the level order # traversal of the binary tree def printlvl(): Q = [] # Push root to the Q.append(root1) while (len(Q)): # Get the front temp = Q[0] # Remove the front Q.pop(0) # Print the data print(temp.data ,end=" ") # Push the left child if (temp.left != None): Q.append(temp.left) # Push the right child if (temp.right != None): Q.append(temp.right) # Driver code # Create the Binary Search Tree root = add(1) root = addinBST(root, 2) root = addinBST(root, 3) root = addinBST(root, 4) root = addinBST(root, 5) # Add nodes of the Binary Search # Tree to the Binary Tree addinorder(root) # Print the level order traversal # of the Binary Tree printlvl() # This code is contributed by SHUBHAMSINGH10 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{// Structure to hold the contents// of the new nodepublic class node { public int data; public node left, right;}static node root1 = null;// Helper function to add and// return the newly added nodestatic node add(int data){ node newnode = new node(); newnode.data = data; newnode.left = newnode.right = null; return newnode;}// Function to add a node to the// Binary Tree in the level orderstatic void addinBT(int data){ // If it is the first node // to be added then make // it the root node if (root1 == null) root1 = add(data); else { Queue<node> Q = new Queue<node>(); Q.Enqueue(root1); while (Q.Count != 0) { // Get and remove the front node temp = Q.Peek(); Q.Dequeue(); // If the left child of the current // node is null then create the new // node here and break if (temp.left == null) { temp.left = add(data); break; } else Q.Enqueue(temp.left); // If the right child of the current // node is null then create the new // node here and break if (temp.right == null) { temp.right = add(data); break; } else Q.Enqueue(temp.right); } }}// Function to add a node to// the Binary Search treestatic node addinBST(node root, int data){ // If the current node is null // then create a new node here // with the given data if (root == null) root = add(data); // If the data is smaller than the // current node's data then recur // for the left sub-tree else if (data < root.data) root.left = addinBST(root.left, data); // Else recur for the right sub-tree else root.right = addinBST(root.right, data); return root;}// Function to perform a level order// insertion in the Binary Tree from// the given Binary Search treestatic void addinorder(node root){ if (root == null) return; addinorder(root.left); addinBT(root.data); addinorder(root.right);}// Function to print the level order// traversal of the binary treestatic void printlvl(){ Queue<node> Q = new Queue<node>(); // Push root to the queue Q.Enqueue(root1); while (Q.Count != 0) { // Get the front node temp = Q.Peek(); // Remove the front Q.Dequeue(); // Print the data Console.Write(temp.data + " "); // Push the left child if (temp.left != null) Q.Enqueue(temp.left); // Push the right child if (temp.right != null) Q.Enqueue(temp.right); }}// Driver codepublic static void Main(String[] args){ // Create the Binary Search Tree node root = null; root = addinBST(root, 1); root = addinBST(root, 2); root = addinBST(root, 3); root = addinBST(root, 4); root = addinBST(root, 5); // Add nodes of the Binary Search // Tree to the Binary Tree addinorder(root); // Print the level order traversal // of the Binary Tree printlvl();}}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of the approach// Structure to hold the contents// of the new nodeclass node { constructor() { this.data = 0; this.left = null; this.right = null; }}var root1 = null;// Helper function to add and// return the newly added nodefunction add(data){ var newnode = new node(); newnode.data = data; newnode.left = newnode.right = null; return newnode;}// Function to add a node to the// Binary Tree in the level orderfunction addinBT(data){ // If it is the first node // to be added then make // it the root node if (root1 == null) root1 = add(data); else { var Q = []; Q.push(root1); while (Q.Count != 0) { // Get and remove the front var temp = Q[0]; Q.shift(); // If the left child of the current // node is null then create the new // node here and break if (temp.left == null) { temp.left = add(data); break; } else Q.push(temp.left); // If the right child of the current // node is null then create the new // node here and break if (temp.right == null) { temp.right = add(data); break; } else Q.push(temp.right); } }}// Function to add a node to// the Binary Search treefunction addinBST(root, data){ // If the current node is null // then create a new node here // with the given data if (root == null) root = add(data); // If the data is smaller than the // current node's data then recur // for the left sub-tree else if (data < root.data) root.left = addinBST(root.left, data); // Else recur for the right sub-tree else root.right = addinBST(root.right, data); return root;}// Function to perform a level order// insertion in the Binary Tree from// the given Binary Search treefunction addinorder(root){ if (root == null) return; addinorder(root.left); addinBT(root.data); addinorder(root.right);}// Function to print the level order// traversal of the binary treefunction printlvl(){ var Q = []; // Push root to the queue Q.push(root1); while (Q.Count != 0) { // Get the front var temp = Q[0]; // Remove the front Q.shift(); // Print the data document.write(temp.data + " "); // Push the left child if (temp.left != null) Q.push(temp.left); // Push the right child if (temp.right != null) Q.push(temp.right); }}// Driver code// Create the Binary Search Treevar root = null;root = addinBST(root, 1);root = addinBST(root, 2);root = addinBST(root, 3);root = addinBST(root, 4);root = addinBST(root, 5);// Add nodes of the Binary Search// Tree to the Binary Treeaddinorder(root);// Print the level order traversal// of the Binary Treeprintlvl();</script> |
Output:
1 2 3 4 5
Time Complexity: O(N).
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!
